【Leetcode Top 100】142. 环形链表 II
问题背景
给定一个链表的头节点 h e a d head head，返回链表开始入环的第一个节点。 如果链表无环，则返回 n u l l null null。
如果链表中有某个节点，可以通过连续跟踪 n e x t next next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 p o s pos pos 来表示链表尾连接到链表中的位置（索引从 0 0 0 开始）。如果 p o s pos pos 是 − 1 -1 −1，则在该链表中没有环。注意： p o s pos pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
数据约束
- 链表中节点的数目范围在范围 [ 0 , 1 0 4 ] [0, 10 ^ 4] [0,104] 内
- − 1 0 5 ≤ N o d e . v a l ≤ 1 0 5 -10 ^ 5 \le Node.val \le 10 ^ 5 −105≤Node.val≤105
- p o s pos pos 的值为 − 1 -1 −1 或者链表中的一个有效索引
解题过程
经典找入环节点，流程主要分为两个阶段：
- 定义快慢指针，用找环的方式让两个指针相遇。
- 复用快指针或者重新定义一个指针从头出发，与慢指针同时后移，两指针相遇的节点即为入环节点。
不复用快指针的情况下上述流程可以在一个循环里实现，时间复杂度是不变的。由于快慢指针相遇时最多完整地遍历一次链表，时间复杂度是 O ( N ) O(N) 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;}
}