环形链表II

142. 环形链表 II

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。

示例 1：

1
2
3

输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。

方法一：快慢指针

在环形链表中，我们使用快慢指针，快慢指针相遇则链表中有环。我们具体分析相遇时的情况：

假设相遇的点在图中红点处，快慢指针在快指针走了 n 圈后相遇，快指针走过的总路程为 a + n(b + c) + b，慢指针走过的总路程为a + b，由于快指针走过的路程是慢指针走过路程的两倍，故a + n(b + c) + b == 2(a + b)，得到a = (n - 1)(b + c) + c，到这里我们发现从相遇点到入环点的距离加上 n - 1 圈的环长，恰好等于从链表头部到入环点的位置。

在快慢指针相遇时，让另外一个指针 ptr 从链表头开始向后走，同时让慢指针在环中走，当两个指针相遇时，ptr 指向的结点就是环的入口，此时慢指针走过的路程为(n - 1)(b + c) + c。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null){
            return null;
        }
        ListNode slow = head, fast = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;

            if(slow == fast){
                ListNode ptr = head;
                while(ptr != slow){
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }
        return null;
    }
}

时间复杂度O(n)
空间复杂度O(1)

方法二：哈希表

使用一个哈希表存储已经访问过的结点，发现当前访问过的结点存在于哈希表，返回当前结点。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode pos = head;
        Set<ListNode> visited = new HashSet<>();
        while(pos != null){
            if(visited.contains(pos)){
                return pos;
            }
            visited.add(pos);
            pos = pos.next;
        }
        return null;
    }
}

时间复杂度O(n)
空间复杂度O(n)