企业官网建设流程全解析

题目概览

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

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

不允许修改链表。

示例 1：

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

示例 2：

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

示例 3：

输入：head = [1], pos = -1输出：返回 null解释：链表中没有环。

提示：

• 链表中节点的数目范围在范围[0, 104]内
• -105 <= Node.val <= 105
• pos的值为-1或者链表中的一个有效索引

进阶：你是否可以使用O(1)空间解决此题？

来源：142. 环形链表 II - 力扣（LeetCode）

解题分析

方法一：哈希集合

用哈希集合存储遍历过的节点，每次遍历判断即可。

时间复杂度：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) { Set<ListNode> set = new HashSet<>(); ListNode temp = head; while(temp != null) { if (set.contains(temp)) { return temp; } set.add(temp); temp = temp.next; } return null; } }

方法二：快慢指针

定义快慢指针，一个遍历一个节点，一个遍历两个节点，如果存在环，则两个指针一定会相遇。
令头节点到环点的距离为 a，从环点到相遇点的距离为 b，环长为 c，快指针转了 n 圈才相遇。因此可以得到快指针移动的距离为 a + nc + b。
由于快指针的速度是慢指针的两倍，因此移动距离也是两倍，慢指针的距离为 a + b，则可以得到 a + nc + b = 2 * ( a + b ) 等价于 a + b = nc。慢指针当前位置是在 b，再往前走 a 的距离就刚好一圈，走到的位置刚好就是环点。
因此我们再相遇时，再定义一个指针从表头出发，当该指针和慢指针相遇时，慢指针刚好走完一圈，指针刚好停留在环点。

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

/** * 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 a = head, b = head; int times; while(true) { if (a == null || b == null || b.next == null) { return null; } a = a.next; b = b.next.next; if (a == b) { break; } } ListNode c = head; while(c != a) { a = a.next; c = c.next; } return c; } }