面试题快慢链表和快慢指针

快慢链表和快慢指针是算法中常见的一种技巧。它们在链表中查找中间节点、判断链表是否有环等情况下十分实用。下面就对快慢链表和快慢指针的使用进行详细讲解。

快慢指针

快慢指针的基本思想是将两个指针指向链表的头节点，快指针每次走两步，慢指针每次走一步，当快指针走到链表的末尾时，慢指针指向的就是链表的中间节点。

示例 1： 找到链表的中间节点

我们有一个链表，包含以下元素：1→2→3→4→5。

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);

为了找到链表的中间节点，我们使用快慢指针的方式。

public ListNode middleNode(ListNode head) {
    ListNode fast = head, slow = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

上面的代码中，我们先将快慢指针都指向链表的头节点，然后移动指针。快指针每次向后移动两个节点，慢指针每次向后移动一个节点，当快指针到链表的末尾时，慢指针所指向的就是链表的中间节点。

示例 2： 判断链表是否为回文链表

问题描述：给定一个单链表，判断它是否为回文链表。

解决方案：使用快慢指针找到链表的中点，然后将链表的后半部分反转。最后将前半部分和后半部分进行对比，如果相同，则说明该链表是回文的。

public boolean isPalindrome(ListNode head) {
    if (head == null) return true;
    ListNode middleNode = middleNode(head);
    ListNode secondHalf = reverse(middleNode.next);
    ListNode p1 = head, p2 = secondHalf;
    boolean result = true;
    while (result && p2 != null) {
        if (p1.val != p2.val) {
            result = false;
        }
        p1 = p1.next;
        p2 = p2.next;
    }
     // 将链表还原
    middleNode.next = reverse(secondHalf);
    return result;
}

// 反转后半部分链表
public ListNode reverse(ListNode head) {
    ListNode prev = null, curr = head;
    while (curr != null) {
        ListNode tmp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = tmp;
    }
    return prev;
}

在上面的代码中，我们使用快慢指针寻找链表的中点，并将中点后面的链表反转，然后将前半部分和后半部分分别赋值给p1和p2，进行对比即可。

快慢链表

快慢链表的基本思想是将链表的指针指向头节点，同时让两个指针同时向前移动。快指针每次移动两个节点，慢指针每次移动一个节点。当快指针到达链表末尾时，慢指针到达链表中点。

示例 1： 判断链表是否有环

问题描述：给定一个链表，判断该链表是否有环。

解决方法：使用快慢链表，如果链表中有环，则快指针最终一定会追上慢指针，如果没有，则快指针会走到链表的末尾。

public boolean hasCycle(ListNode head) {
    ListNode fast = head, slow = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            return true;
        }
    }
    return false;
}

上面的代码中，我们使用快慢链表遍历链表，如果链表中有环，则快指针最终会追上慢指针，如果没有环，则快指针到达链表的末尾时退出循环。

示例 2： 寻找环的起点

问题描述：给定一个链表，如果链表中有环，找到环的起点。

解决方法：使用快慢链表，如果指针相遇，说明链表中有环。然后将两个指针移动到链表的头节点处，然后同时移动两个指针，每次移动一个节点，当两个指针再次相遇时，该节点即为环的起点。为什么这么做是正确的呢？因为当两个指针相遇时，假设慢指针所走的距离为S1，环的周长为C，相遇时慢指针走了n个环，那么此时快指针走了2n个环，快指针从开始到相遇所走的路程为S1 + nC，而快指针从开始到相遇所走的路程为 2(S1 + nC)。因为快指针所走的路程是慢指针的两倍，因此我们可以推出 S1 = (n-1)C + (C-S2)，其中S2是慢指针所走的距离。根据上面的公式，我们将快指针再移动n-1个环，此时快指针到达环的起点处，同时，我们让慢指针从头节点开始移动，当两个指针相遇时，即为环的起点。

public ListNode detectCycle(ListNode head) {
    ListNode fast = head, 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) {
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
}

上面的代码中，我们先使用快慢链表判断链表是否有环，如果链表中有环，则快慢指针会相遇。接下来，我们将快指针指向头节点，然后将快慢指针同时向前移动，当两个指针再次相遇时，该节点即为环的起点。