快慢指针-环形链表的起点计算

142. 环形链表

这里是普通哈希表解法

public class Solution {
    public ListNode detectCycle(ListNode head) {
        // 解法一：
        // base case
        if (head == null) {
            return null;
        }
        // 使用hashmap
        HashSet<ListNode> map = new HashSet<>();
        int pos = 0;
        while (head != null) {
            map.add(head);
            
            if (map.contains(head.next) && map.contains(head.next.next)) {
                return head.next;
            }
            head = head.next;
            pos++;
        }
        return null;
    }
}

这里是快慢指针解法

public class Solution {
    public ListNode detectCycle(ListNode head) {
        // 解法二：快慢指针
        // base case
        if (head == null || head.next == null) {
            return null;
        }
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (fast == slow) {
                break;
            }
        }
        // 开始计算环的起点
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}

解法二的精髓在于，快慢指针的快指针每次移动两步，慢指针每次移动一步，当快慢指针相遇时，慢指针回到起点，快、慢指针每次都移动一步，当快慢指针再次相遇时，相遇点就是环的起点。

为什么呢？直接上图证明：