链表-双指针

单链表的倒数第 K 个结点

从前往后寻找单链表的第 k 个结点，只要顺序遍历链表就找到了，但是如何寻找从后往前数的第 k 个结点呢？

假设链表有 n 个结点，倒数第 k 个节点就是正数第 n - k + 1 个结点
但是单链表只能顺序遍历，必须先顺序遍历一遍，先计算出 n ，然后再遍历链表计算第 n - k + 1 个结点
即需要遍历两次链表才能得出倒数第 k 个结点

那么能不能只遍历一次链表就算出倒数第 k 个结点？

假设 k = 2，首先，先让一个指针 p1 指向链表的头节点 head，然后走 k 步：

现在的 p1，只要再走 n - k 步，就能走到链表末尾的空指针了
趁这个时候，再用一个指针 p2 指向链表头节点 head：

接下来就很显然了，让 p1 和 p2 同时向前走，p1 走到链表末尾的空指针时前进了 n - k 步，p2 也从 head 开始前进了 n - k 步，停留在第 n - k + 1 个节点上，即恰好停链表的倒数第 k 个节点上：

这样，只遍历了一次链表，就获得了倒数第 k 个节点 p2。

/**
 * 查找倒数第 k 个结点：
 * 1）让 p1 和 p2 指向头结点
 * 2）让 p1 先走 k 步
 * 3）让 p1 和 p2 同时走，直至 p1 走到尾结点
 * 4）此时 p2 指向的结点就是倒数第 k 个结点
 *
 * @param head
 * @param k
 * @return
 */
ListNode findFromEnd(ListNode head, int k) {
    ListNode p1 = head;
    ListNode p2 = head;
    // p1 先走 k 步
    for (int i = 0; i < k; i++) {
        p1 = p1.next;
    }
    // p1 和 p2 同时走，直至 p1 走到尾结点
    while (p1 != null) {
        p1 = p1.next;
        p2 = p2.next;
    }
    // 此时 p2 指向第 n - k 个节点
    return p2;
}

单链表的中点

常规方法也是先遍历链表计算 n，再遍历一次得到第 n / 2 个节点，也就是中间节点。

如果想一次遍历就得到中间节点，需要使用「快慢指针」的技巧：
让两个指针 slow 和 fast 分别指向链表头结点 head。
每当慢指针 slow 前进一步，快指针 fast 就前进两步，这样，当 fast 走到链表末尾时，slow 就指向了链表中点。

ListNode middleNode(ListNode head) {
    // 快慢指针都指向头结点
    ListNode fast = head;
    ListNode slow = head;
    // 快指针走到末尾时停止
    while(fast != null && fast.next != null) {
        // 慢指针走一步，快指针走两步
        slow = slow.next;
        fast = fast.next.next;
    }
    // 慢指针指向中点
    return slow;
}

如果链表长度为偶数，也就是说中点有两个的时候，这个解法返回的节点是靠后的那个节点。

判断链表是否包含环

每当慢指针 slow 前进一步，快指针 fast 就前进两步。
如果 fast 最终遇到空指针，说明链表中没有环；如果 fast 最终和 slow 相遇，那肯定是 fast 超过了 slow 一圈，说明链表中含有环。
类似于跑圈慢的被快的套圈

boolean hasCycle(ListNode head) {
    // 快慢指针都指向头结点
    ListNode fast = head;
    ListNode slow = head;
    // 快指针走到末尾时停止
    while(fast != null && fast.next != null) {
        // 慢指针走一步，快指针走两步
        slow = slow.next;
        fast = fast.next.next;
        // 快慢指针相遇，说明有环
        if (slow == fast) {
            return true;
        }
    }
    // 没有环
    return false;
}

这个问题还有进阶版：如果链表中含有环，如何计算这个环的起点？

ListNode detectCycle(ListNode head) {
    // 快慢指针都指向头结点
    ListNode fast = head;
    ListNode slow = head;
    // 快指针走到末尾时停止
    while(fast != null && fast.next != null) {
        // 慢指针走一步，快指针走两步
        slow = slow.next;
        fast = fast.next.next;
        // 快慢指针相遇，说明有环，此时中断
        if (slow == fast) {
            break;
        }
    }
    if (fast == null || fast.next == null) {
        // 没有环
        return null;
    }
    // 慢指针重新指向头结点
    slow = head;
    // 快慢指针同步前进，相交点就是环起点
    while(slow != fast) {
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
}

当快慢指针相遇时，让其中任一个指针指向头节点，然后让它俩以相同速度前进，再次相遇时所在的节点位置就是环开始的位置。

我们假设快慢指针相遇时，慢指针 slow 走了 k 步，那么快指针 fast 一定走了 2k 步：

fast 一定比 slow 多走了 k 步，这多走的 k 步其实就是 fast 指针在环里转圈圈，所以 k 的值就是环长度的「整数倍」。

假设相遇点距环的起点的距离为 m，那么结合上图的 slow 指针，环的起点距头结点 head 的距离为 k - m，也就是说如果从 head 前进 k - m 步就能到达环起点。

巧的是，如果从相遇点继续前进 k - m 步，也恰好到达环起点。因为结合上图的 fast 指针，从相遇点开始走k步可以转回到相遇点，那走 k - m 步肯定就走到环起点了：

所以，只要我们把快慢指针中的任一个重新指向 head，然后两个指针同速前进，k - m 步后一定会相遇，相遇之处就是环的起点了。

两个链表是否相交

给你输入两个链表的头结点 headA 和 headB，这两个链表可能存在相交。
如果相交，你的算法应该返回相交的那个节点；如果没相交，则返回 null。

那么我们的算法应该返回 c1 这个节点。

这个题直接的想法可能是用 HashSet 记录一个链表的所有节点，然后和另一条链表对比，但这就需要额外的空间。

如果不用额外的空间，只使用两个指针，你如何做呢？

难点在于，由于两条链表的长度可能不同，两条链表之间的节点无法对应：

如果用两个指针 p1 和 p2 分别在两条链表上前进，并不能同时走到公共节点，也就无法得到相交节点 c1。

解决这个问题的关键是，通过某些方式，让 p1 和 p2 能够同时到达相交节点 c1。

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

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

那你可能会问，如果说两个链表没有相交点，是否能够正确的返回 null 呢？

这个逻辑可以覆盖这种情况的，相当于 c1 节点是 null 空指针嘛，可以正确返回 null。

ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    // p1 指向 A 链表头结点 p2 指向 B 链表头结点
    ListNode p1 = headA;
    ListNode p2 = headB;
    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;
        }
    }
    return p1;
}