链表的逻辑相关，寻找倒数第 K 个节点、寻找中间位置、判断是否有环、判断两个链表是否相交等

本章主要介绍链表相关的逻辑操作，包括寻找倒数第 K 个节点、寻找中间位置、判断是否有环、判断两个链表是否相交等。

寻找倒数第 K 个节点

链表不同于数组，一开始并不知道长度，可通过找数据规律求解，如链表长度为 n，倒数第 K 个节点转化过来即为顺数第 n-K+1 个节点，可通过先遍历整个链表得出长度 n，再第二次遍历到n-K+1得到寻找节点。

但是上述需要循环两次遍历。

我们也可以通过一次遍历来实现（最优解）。运用双指针，指针 p1 从头结点先走 k 步，距离末尾空指针还剩 n-k 步，此时让 p2 指向链表头结点，p1 和 p2 同时走 n-k 步，此时 p2 在链尾 null，p1 正好在顺数第 n-K+1 个节点，即为倒数第 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，然后在遍历 n/2寻找中间位置。

但是最优解可以通过一次循环来实现。

运用 快慢指针 的思想，让两个指针 slow fast 同时从头结点出发， slow 走一步,fast 走两步，当 fast 为空或者 fast 的下一节点为空，slow 则走到了中点位置，即为所求。算法如下：

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

判断链表是否有环

思想也为运用 快慢指针，让两个指针 slow fast 同时从头结点出发， slow 走一步,fast 走两步，如果两个指针相遇在同一位置，则证明有环；当 fast 为空或者 fast 的下一节点为空，则证明没有环，算法如下：

boolean hasCycle(ListNode head) {
    // 快慢指针初始化指向 head
    ListNode slow = head, fast = head;
    // 快指针走到末尾时停止
    while (fast != null && fast.next != null) {
        // 慢指针走一步，快指针走两步
        slow = slow.next;
        fast = fast.next.next;
        // 快慢指针相遇，说明含有环
        if (slow == fast) {
            return true;
        }
    }
    // 不包含环
    return false;
}

判断两个链表是否相交，并返回相交节点

此解法我们可以做如下模拟，其中两个链表相交的点为 3

链表1 1,3,5,6,7,

链表2 2,3,4,8,9,
,
然后把链表拼接如下

链表1 + 链表2 = 1,3,5,6,7,2,3,4,8,9

链表2 + 链表1 = 2,3,4,8,9,1,3,5,6,7

可以看出两条链表拼接之后，用两个指针分别同时前进，遇到相遇时，该节点即为相交节点。算法如下：

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