【Leetcode Top 100】142. 环形链表 II

问题背景

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

数据约束

• 链表中节点的数目范围在范围 $[0,10^4]$ 内
• $-10^5\le Node.val\le 10^5$
• $pos$ 的值为 $-1$ 或者链表中的一个有效索引

解题过程

经典找入环节点，流程主要分为两个阶段：

1. 定义快慢指针，用找环的方式让两个指针相遇。
2. 复用快指针或者重新定义一个指针从头出发，与慢指针同时后移，两指针相遇的节点即为入环节点。

不复用快指针的情况下上述流程可以在一个循环里实现，时间复杂度是不变的。由于快慢指针相遇时最多完整地遍历一次链表，时间复杂度是 $O(N)$ 量级的，需要常数级别的额外空间。

具体实现

/*** 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 slow = head, fast = head, nextTurn = head;while(fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if(slow == fast) {while(slow != nextTurn) {slow = slow.next;nextTurn = nextTurn.next;}return slow;}}return null;}
}