链表双指针技巧总结

链表双指针技巧总结(持续更新)

合并两个有序链表

https://leetcode.cn/problems/merge-two-sorted-lists/description/

这里有两个注意的点，一个是虚拟头节点，一个是双指针

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 虚拟头结点。这里我们创建了一个虚拟头节点，方便后续操作。
        ListNode dummy = new ListNode(-1), p = dummy;//p指针指向了虚拟头节点
        ListNode p1 = l1, p2 = l2;//p1和p2分别指向l1和l2的第一个节点
    
        while (p1 != null && p2 != null) {


            // 比较 p1 和 p2 两个指针
            // 将值较小的的节点接到 p 指针
            if (p1.val > p2.val) {//如果p2更小，就把虚拟头节点的next指向p2，然后p2前进一个节点
                p.next = p2;
                p2 = p2.next;
            } else {//如果p1更小，就把虚拟头节点的next指向p1，然后p1前进一个节点
                p.next = p1;
                p1 = p1.next;
            }
            // p 指针不断前进
            p = p.next;//p节点的next指针被赋值后，p节点向后移动一位
        }
        
        //如果有l1和l2有一个链表还有剩余节点，就把p的next都指向剩余的节点
        if (p1 != null) {
            p.next = p1;
        }
        
        if (p2 != null) {
            p.next = p2;
        }
        
        return dummy.next;//由于我们的p是虚拟的头节点，真正合并完的链表是虚拟头节点做成的链表的下一位
    }
}

单链表的分解

https://leetcode.cn/problems/partition-list/description/

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你应当 保留 两个分区中每个节点的初始相对位置。

解题思路就是把这个链表拆成两个链表，一个链表的元素大小都小于x，另一个链表的元素大小都大于等于x，最后再把这两个链表接在一起

//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        // 存放小于 x 的链表的虚拟头结点
        ListNode dummy1 = new ListNode();
        // 存放大于等于 x 的链表的虚拟头结点
        ListNode dummy2 = new ListNode();
        // p1, p2 指针负责生成结果链表
        ListNode p1 = dummy1;
        ListNode p2 = dummy2;
        ListNode p = head;

        while (p !=null){
            if (p.val >= x){
                p1.next = p;
                p1 = p1.next;
            }else {
                p2.next = p;
                p2 = p2.next;
            }

            //这里不可以直接让p的指针移动，因为我们的这个p是在原来的链表上进行操作的
            //所以这里我们应该断开原链表，再让p指向下一个节点
            ListNode temp = p.next;
            p.next = null;
            p = p.next;
        }

        //这里的p1和p2已经变成了这两个拆开的链表的末尾元素节点，所以这里我们用p1的next指针指向的是dummy2的头结点，就把他们连起来了
        p1.next = dummy2.next;

        //最后返回的是p1指针所在的这个小于x的链表的.next，因为要处理虚拟头节点，所以真实的节点是在后一位
        return dummy1.next;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

合并k个有序链表

https://leetcode.cn/problems/merge-k-sorted-lists/description/

这里我们就可以使用优先级队列。优先级队列中可以进行自动排序

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) return null;
        // 虚拟头结点
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        // 优先级队列，最小堆,这里就是创建一个优先级队列，有一个lamda表达式，这个lambda表达式就是a比b大就把a先放进这个优先级队列里面，前面的就是小的从小到大排序
        PriorityQueue<ListNode> pq = new PriorityQueue<>(
            lists.length, (a, b)->(a.val - b.val));
        // 将 k 个链表的头结点加入最小堆。注意：这里加入到最小堆的是头结点，比如我们有 3 个有序链表， [[1,4,5],[1,3,4],[2,6]]就把1，1，2 三个头结点放进去，自动排序
        for (ListNode head : lists) {
            if (head != null) {
                pq.add(head);
            }
        }

        while (!pq.isEmpty()) {
            // 获取最小节点，接到结果链表中
            ListNode node = pq.poll();//把头节点里面最小的值拿出来
            p.next = node;
            //这里就是排序头节点，把最小的头结点拿出来后，如果这个头结点所在的链表后面还有值，然后把这个推出来的这个最小头结点后面的值放进优先级队列，和另外的两个数字比较，再拿出来最小的数字
            if (node.next != null) {
                pq.add(node.next);
            }
            // p 指针不断前进
            p = p.next;
        }
        return dummy.next;
    }
}

优先队列 pq 中的元素个数最多是 k，因为优先级队列要进行一个个排序，所以一次 poll 或者 add 方法的时间复杂度是 O(logk)；

所有的链表节点有N个都会被加入和弹出 pq，所以算法整体的时间复杂度是 O(Nlogk)，其中 k 是链表的条数，N 是这些链表的节点总数。