双指针之链表总结

一共七个题，且只涉及到单链表的操作。

1. 合并两个有序链表 合并两个有序链表

2. 链表的分解 分隔链表

3. 合并 k 个有序链表 合并K个升序链表：

4. 寻找单链表的倒数第 k 个节点 剑指 Offer 22. 链表中倒数第k个节点

5. 寻找单链表的中点 链表的中间结点

6. 判断单链表是否包含环并找出环起点 环形链表 II

7. 判断两个单链表是否相交并找出交点 相交链表

合并两个有序链表

将两个升序链表合并成为一个新的升序链表。新链表通过拼接给定的两个链表所有节点组成。

方法签名：

ListNode mergeTwoLists(ListNode l1, ListNode l2);

思路：

善用虚拟头节点，使用dummy生成一个虚拟节点p，同时为了不破坏l1和l2的链表结构，（因为要遍历这两个链）所以，重新赋值l1给p1，l2给p2；

在while循环里面，每次比较p1和p2的大小，将较小的节点给p，同时p指针不断后移。

关键代码：

while (p1 != null && p2 != null) {

       // 比较 p1 和 p2 两个指针
       // 将值较小的的节点接到 p 指针
       if (p1.val > p2.val) {
           p.next = p2;
           p2 = p2.next;
       } else {
           p.next = p1;
           p1 = p1.next;
       }
       // p 指针不断前进
       p = p.next;
   }

什么时候使用虚拟头节点？

需要创建一个新的链表的时候，可以使用虚拟头节点简化边界情况的处理。

分割链表

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

你应该保留两个分区的每个节点初试相对位置。

在合并两个有序链表时，让你合二为一，而这里需要分解，使得原链表一分为二。具体来说，我们可以将原链表分成两个小链表，一个链表中的元素都小于x，另外一个链表中的元素都大于等于x，最后将这两条链表连在一起，就得到了最终答案：

题解：

ListNode partition(ListNode head, int x) {
    // 存放小于 x 的链表的虚拟头结点
    ListNode dummy1 = new ListNode(-1);
    // 存放大于等于 x 的链表的虚拟头结点
    ListNode dummy2 = new ListNode(-1);
    // p1, p2 指针负责生成结果链表
    ListNode p1 = dummy1, p2 = dummy2;
    // p 负责遍历原链表，类似合并两个有序链表的逻辑
    // 这里是将一个链表分解成两个链表
    ListNode p = head;
    while (p != null) {
        if (p.val >= x) {
            p2.next = p;
            p2 = p2.next;
        } else {
            p1.next = p;
            p1 = p1.next;
        }
        // 断开原链表中的每个节点的 next 指针
        ListNode temp = p.next;
        p.next = null;
        p = temp;
    }
    // 连接两个链表
    p1.next = dummy2.next;

    return dummy1.next;
}

合并K个有序链表

问题

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

题解

合并k个有序链表类似于合并两个有序链表，难点在于如何获取k个节点中最小的节点，并接到结果链上。

使用优先队列，遍历每个链表，将链表中的每个节点都添加到最小堆中，就可以获取k个节点中的最小节点了。

先入队列，然后出队列，最后的条件是队列是否为空！

核心代码：

// 优先级队列，最小堆
   PriorityQueue<ListNode> pq = new PriorityQueue<>(
       lists.length, (a, b)->(a.val - b.val));
   // 将 k 个链表的头结点加入最小堆
   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;
   }

单链表的倒数第K个节点

题目：

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例：

给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

题解

是否可以用栈来实现？目前存疑。

给出的思路：用双指针，也叫快慢指针吧，快指针先走k步，然后快、慢指针再一起走，当快指针走到头的时候，慢指针就是倒数第k个节点。

// 返回链表的倒数第 k 个节点
ListNode findFromEnd(ListNode head, int k) {
    ListNode p1 = head;
    // p1 先走 k 步
    for (int i = 0; i < k; i++) {
        p1 = p1.next;
    }
    ListNode p2 = head;
    // p1 和 p2 同时走 n - k 步
    while (p1 != null) {
        p2 = p2.next;
        p1 = p1.next;
    }
    // p2 现在指向第 n - k + 1 个节点，即倒数第 k 个节点
    return p2;
}

删除链表的倒数第N个节点

和单链表的倒数第K个节点一样，只不过需要找到节点后删除。

2023年6月30日更新：

public ListNode removeNthFromEnd(ListNode head, int n) {
       ListNode dummy = new ListNode(-1);
       dummy.next = head;
       // 先利用双指针找到倒数第N个节点
       ListNode p1 = dummy;
       // p1 先走n步
       for (int i = 0; i < n + 1; i++) {
           p1 = p1.next;
       }
       ListNode p2 = dummy;
       // 再一起走
       while (p1 != null){
           p2 = p2.next;
           p1 = p1.next;
       }
       // 现在p2指的节点就是倒数第N个节点
       // 开始删除p2节点
       p2.next = p2.next.next;
       return dummy.next;
   }

单链表的中点

题意

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：head = [1,2,3,4,5]
输出：[3,4,5]
解释：链表只有一个中间结点，值为 3 。

示例 2：

输入：head = [1,2,3,4,5,6]
输出：[4,5,6]
解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。

题解

同样，利用快慢指针的方法，快指针每次走两步，慢指针走一步，这样，让快指针走到头的时候，慢指针正好指在中点。

核心代码：

while (fast != null && fast.next != null) {
        // 慢指针走一步，快指针走两步
        slow = slow.next;
        fast = fast.next.next;
    }

注意，需要判断fast.next是否为null，原因是，有可能是偶数的节点。

判断链表是否包含环

题意

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

题解

也是利用快慢指针，每当慢指针走一步，快指针走两步，如果快指针最终遇到了空指针，则说明链表中没有环；

如果快指针和慢指针相遇，证明快指针超过了慢指针一圈，说明有环。

核心代码：

while (fast != null && fast.next != null) {
       // 慢指针走一步，快指针走两步
       slow = slow.next;
       fast = fast.next.next;
       // 快慢指针相遇，说明含有环
       if (slow == fast) {
           return true;
       }
   }

环形链表II

找到这个环的起点。

思路

当快慢指针相遇的时候，证明快慢指针相遇，让其中任意一个指向头结点，然后让快慢指针以相同的速度前行，再次相遇的节点位置就是环开始的位置。

核心代码：

// 重新指向头结点
       slow = head;

       // 快慢指针同步前进，相交点就是环起点
       while (slow != fast) {
           fast = fast.next;
           slow = slow.next;
       }
       return slow;

两个链表是否相交

给你输入两个链表的头结点 headA 和 headB，这两个链表可能存在相交。

如果相交，你的算法应该返回相交的那个节点；如果没相交，则返回 null。

比如题目给我们举的例子，如果输入的两个链表如下图：

题解

难点：如何让p1和p2两个链表同时到达相交节点

所以，我们可以让 p1 遍历完链表 A 之后开始遍历链表 B，让 p2 遍历完链表 B 之后开始遍历链表 A，这样相当于「逻辑上」两条链表接在了一起。

如果这样进行拼接，就可以让 p1 和 p2 同时进入公共部分，也就是同时到达相交节点 c1

核心代码：

while (p1 != p2) {
        // p1 走一步，如果走到 A 链表末尾，转到 B 链表
        if (p1 == null) p1 = headB;
        else            p1 = p1.next;
        // p2 走一步，如果走到 B 链表末尾，转到 A 链表
        if (p2 == null) p2 = headA;
        else            p2 = p2.next;
    }

参考

双指针技巧秒杀七道链表题目