文章目录

• • 题目
  • 解法一：循环标记
  • • Java代码实现
    • Go 代码实现
    • 复杂度分析
  • 解法二：快慢指针
  • • Java 代码实现
    • Go 代码实现
    • 复杂度分析

这是一道 中等难度 的题，是 判断链表是否有环 的扩展，在有环的情况下返回入环节点， 依然是两种解法。题目来自：leetcode

题目

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
不允许修改 链表。

示例 1：

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

示例 2：

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

示例 3：

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

提示：
● 链表中节点的数目范围在范围 [0,104][0, 10^4][0,104] 内
● −105<=Node.val<=1055-10^5 <= Node.val <= 105^5−105<=Node.val<=1055
● pos 的值为 -1 或者链表中的一个有效索引

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

解法一：循环标记

循环遍历每一个节点并标记为已访问，返回第一次遍历到的已访问节点，否则最后返回 null 。

Java代码实现

/*** 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 visited = new HashSet<>();while(head != null){if(visited.contains(head)){return head;}visited.add(head);head = head.next;}return null;}
}

Go 代码实现

/*** Definition for singly-linked list.* type ListNode struct {*     Val int*     Next *ListNode* }*/
func detectCycle(head *ListNode) *ListNode {visited := make(map[*ListNode]bool)for head != nil {if visited[head]{return head;}visited[head] = truehead = head.Next}return nil}

复杂度分析

时间复杂度 O(N)O(N)O(N)：需要访问链表中的每一个节点，时间复杂度为链表长度n。
空间复杂度 O(N)O(N)O(N)：需要记录每个访问过的节点，空间复杂度为链表的长度n。

解法二：快慢指针

快指针每次走 2 步， 慢指针每次走 1 步，若 快慢指针 能够相遇说明链表有环，但是第一次相遇的点并不一定是入环点，如下所示：

相遇点 7 并不是入口点 4 。

那么怎么找到入环点呢？假如入环点前有 a 个节点，环上有 b 个节点，第一次相遇时快指针走了 f 步，慢指针走了 s 步。

由以上假设可以得知：

1. f = 2s；（快指针走的步数是慢指针的 2 倍）
2. f - s = nb；（快指针比慢指针多走了 n 个环的步数，然后相遇）
   即第一次相遇时，慢指针走了 nb 步，快指针走了 2nb 步。

第一次相遇的点还需要走多少步到达入环点？

因为到达入环点的步数为：a + nb, 其中 n >= 0。现在 慢指针 已经走了 nb 步，那么再走 a 步必定可以到达入环点，但是我们并不知道 a 是多少。

我们可以换个思路，此时可以把 快指针 重新指到起始点 head，即 快慢指针 到达入环点为步数都是 a , 那么当 快慢指针 再次相遇的地方就是入环点了。

完整流程如下：

Java 代码实现

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

Go 代码实现

/*** Definition for singly-linked list.* type ListNode struct {*     Val int*     Next *ListNode* }*/
func detectCycle(head *ListNode) *ListNode {fast, slow := head, headfor fast != nil && fast.Next != nil {fast, slow = fast.Next.Next, slow.Nextif(slow == fast){fast = headfor fast != slow {fast, slow = fast.Next, slow.Next}return fast}}return nil}

复杂度分析

时间复杂度 O(N)O(N)O(N)：时间复杂度为慢指针所走的步数为 nb + a -> (n - 1)b + (a + b) -> (n - 1)b + 链表的总节点数 ，因为 n 和 b 都是是常数，所以复杂度近似为 O(N)O(N)O(N)。
空间复杂度 O(1)O(1)O(1)：只需要记录快慢指针的位置，为常数空间复杂度。