LeetCode题解：环形链表II

题目描述

给定一个链表的头节点head，返回链表开始入环的第一个节点。如果链表无环，则返回null。
如果链表中有某个点，可以通过连续跟踪next指针再次，则链表中存在环，则链表中存在环。为了表示给定链表中的环，测评系统内部使用整数pos来表示链表尾连接到链表中的位置(索引从0开始)。如果pos是-1，则在该链表中没有环。
注意：pos不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改链表

示例

• 示例1
  输入：head = [3,2,0,-4], pos = 1
  输出：返回索引为 1 的链表节点
  解释：链表中有一个环，其尾部连接到第二个节点。
• 示例1
  输入：head = [1], pos = -1
  输出：返回 null
  解释：链表中没有环。

思路方法

1、使用hash表

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode pos = head;
        Set<ListNode> hash = new HashSet<ListNode>();
        while(pos!=null){
            if(hash.contains(pos)){
                return pos;
            }else{
                hash.add(pos);
            }
            pos = pos.next;
        }
        return null;
    }
}

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：O(N)

快慢指针

我们是用两个指针，快指针和慢指针，fast与slow。它们起始都位于链表的头部。随后，slow指针每次向后移动一个位置，而快指针向后移动两个位置。如果链表中存在环，则fast指针最终和slow指针在环中相遇。

此图片来自LeetCode

如图所示，设链表中环外部分的长度为a。slow指针进入环后，又走了b的距离与fast相遇。此时f，ast指针已经走完了环的n圈，因此它走过的总距离为a+n（b+c）+b=a+（n+1）b+nc。
根据题意，此时此刻，fast指针走过的距离都为slow指针的2倍。因此，我们有
a+（n+1）b+nc=2（a+b） -> a=c+（n-1）(b+c)
有了a=c+(n-1)(b+c)的等量关系，我们会发现：从相遇点到入环点的距离加上n-1圈的环长，恰好等于链表头部到入环点的距离。
因此，当发现slow和fast相遇时，我们再额外使用一个指针ptr。起始，它指向链表头部；随后，它和slow每次向后移动一个位置。最终，它们会在入环点相遇。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode slow = head, fast = head;
        while (fast != null) {
            slow = slow.next;
            if (fast.next != null) {
                fast = fast.next.next;
            } else {
                return null;
            }
            if (fast == slow) {
                ListNode ptr = head;
                while (ptr != slow) {
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }
        return null;
    }
}

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：O(1)