题目链接

题目描述

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

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

进阶：

你是否可以使用 O(1) 空间解决此题？
解题思路
1. 哈希表

找重复，直接哈希表解决。

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

时间复杂度：
空间复杂度：
2. 快慢指针

算法流程：

先利用快慢指针判断链表是否有环；

如果有环，此时快慢指针处于同一个节点。设置指针 res 从 head 出发，慢指针不动，快指针每走一圈步后（和慢指针相遇一次说明走了一圈），res 指针就移动一步，当 res 和快指针相遇即为入环的第一个节点。

public class Solution {
  public ListNode detectCycle(ListNode head) {
      ListNode fast = head;
      ListNode slow = head;
      // 1. 判断是否有环
      while (true) {
          if (fast == null || fast.next == null) {
              return null;
          }
          fast = fast.next.next;
          slow = slow.next;
          // 有环
          if (fast == slow) {
              break;
          }
      }
      ListNode res = head;
      while (res != fast) {
          fast = fast.next;
          if (fast == slow) {
              res = res.next;
          }
      }
      return res;
  }
}

时间复杂度：
空间复杂度：
3. 数学 + 快慢指针（最优解）

算法流程：

利用快慢指针判断链表是否有环，如果快慢指针第一次相遇，说明有环；
第一次相遇后，fast 从 head 出发一次走一步，slow 从第一次相遇的节点出发一次走一步，当 fast 和 slow 第二次相遇时，相遇的节点即为链表的入环节点。

上述过程可以通过数学推导出它的正确性：

当第一次相遇时：设从链表头部到入环节点的长度为 x，链表环长为 y。两指针分别走了 f, s 步。
- 已知 fast 指针走的步数是 slow 指针走的步数的 2 倍，可得；
- fast 指针走的路程是 slow 指针的路程 + 环长的整数倍，即：；（双指针都走过 x 步，然后在环内直至重合，重合时 fast 比 slow 多走环的整数倍）；
- 两式详见可得：，代入第二个式子可得：。
如果让指针从链表头部一直向前走并统计步数 k，那么所有 走到链表入口节点时的步数 是：。（先走 x 步到入口节点，之后每绕一圈都会再次到入口节点）。

而目前，slow 指针走过的步数为 LeetCode142. 环形链表 II - 图10 步，再走 x 步即为入口节点，而从 head 到入口节点的就是要走 x 步，因此只需要构建一个指针从 head 出发走 x 步，slow 也走 x 步，当两指针重合时即为链表的入口节点。

public class Solution {
  public ListNode detectCycle(ListNode head) {
      ListNode fast = head;
      ListNode slow = head;
      // 1. 判断是否有环
      while (true) {
          if (fast == null || fast.next == null) {
              return null;
          }
          fast = fast.next.next;
          slow = slow.next;
          // 有环
          if (fast == slow) {
              break;
          }
      }
      fast = head;
      while (fast != slow) {
          fast = fast.next;
          slow = slow.next;
      }
      return slow;
  }
}

时间复杂度：
空间复杂度：

LeetCode142. 环形链表 II

题目链接

题目描述

解题思路

1. 哈希表

2. 快慢指针

3. 数学 + 快慢指针（最优解）