链表、二叉树与回溯（十一）

About 696 wordsAbout 2 min

algolinklistleetcode

2024-01-25

一、链表

1、合并两个有序链表

leetcode 第 21 题，合并两个升序的链表，用一个虚拟节点和两个移动指针来解决，判断指针处的节点的大小，插入到虚拟节点后方

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 虚拟头结点
        ListNode dummy = new ListNode(-1), p = dummy;
        ListNode p1 = list1, p2 = list2;

        while(p1!=null && p2 !=null){
            if(p1.val > p2.val){
                p.next = p2;
                p2 = p2.next;
            }
            else{
                p.next = p1;
                p1 = p1.next;  // 指针往后移动一位
            }
            p = p.next;  // 移动p
        }
        // 添加上后面没有循环完的节点
        if(p1!=null){
            p.next = p1;
        }
        if(p2!=null){
            p.next = p2;
        }
        return dummy.next;
    }
}

2、分割链表

class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode dummy1 = new ListNode(-1);  // 两个虚拟头结点
        ListNode dummy2 = new ListNode(-1);

        ListNode p1 = dummy1, p2 = dummy2;  // 两个可移动的节点
        ListNode p = head;
        while(p != null){
            if(p.val >= x){  // 判断节点值的大小，放到对应链表节点后面
                p2.next = p;
                p2 = p2.next;
            }
            else{
                p1.next = p;
                p1 = p1.next;
            }
            ListNode tmp = p.next;  // 原链表指针移动
            p.next = null;
            p = tmp;
        }
        // 合并两个链表
        p1.next = dummy2.next;  // 链接两个链表
        return dummy1.next;  // 返回链表。

    }
}

3、合并 k 个升序的链表

这里用到一个二叉堆的数据结构，先明白如何用，再说是怎样实现的，就是使用一个优先级队列来处理，先把条件给出来的链表放到优先级队列里面，后面每次在 pull 出来最小的节点，放到虚拟节点的后面。

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0){
            return null;
        }
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        PriorityQueue<ListNode> pq = new PriorityQueue<>(
            lists.length, (a, b)->(a.val - b.val)   // a.val - b.val 最小堆
        );
        // put ListNode head in priorityQueue
        for(ListNode head: lists){
            if(head!= null){  // if head != null
                pq.add(head);
            }
        }
        while(!pq.isEmpty()){  // pq is not empty, pull minest node
            ListNode node = pq.poll();
            p.next = node;
            if(node.next!=null){
                pq.add(node.next);
           }
           p = p.next;
        }
        return dummy.next;
    }
}