剑指offer-55、链表中环的⼊⼝节点

题⽬描述

给⼀个链表，若其中包含环，请找出该链表的环的⼊⼝结点，否则，输出null 。
例如，输⼊{1,2},{3,4,5} 时，对应的环形链表如下图所示：

可以看到环的⼊⼝结点的结点值为3，所以返回结点值为3的结点。
给定的链表节点的结构：

1. public class ListNode {
2.     int val;
3.     ListNode next = null;
4.     ListNode(int val) {
5.             this.val = val;
6.     }
7. }

复制代码

思路及解答

借用HashSet

直接使⽤ HashSet ,历链表的时候，如果 HashSet 中不包含，则添加到 HashSet 中，如果链表中包含，说明已经回到环的第⼀个节点。Java 代码实现如下：

1. public ListNode EntryNodeOfLoop(ListNode pHead) {
2.     HashSet set = new HashSet();
3.     while(pHead!=null){
4.         if(set.contains(pHead)){
5.                 return pHead;
6.         }else{
7.             set.add(pHead);
8.             pHead = pHead.next;
9.         }
10.     }
11.     return null;
12. }

复制代码

• 时间复杂度：O(n) - 每个节点最多访问一次
  
• 空间复杂度：O(n) - 最坏情况下需要存储所有节点
  

双指针

上⾯的做法时间复杂度为O(n) ，由于借助了⼀个hashSet ，空间复杂度也为O(n) 。那假设我们不需要使⽤额外的空间呢？怎么做呢？
使⽤快慢双指针，⼀个⼀次⾛⼀步，⼀个⼀次⾛两步，当两个重合在⼀起的时候，这时候，并不是环的⼊⼝节点。只能说明两个指针，⼀个⽐另外⼀个多⾛了若⼲圈，可能是⼀圈，可能是2 ， 3 圈。

⽐如上⾯的，如果开始节点是A ，环的⼊⼝是B ，相遇的节点是C ，那么

• 慢指针⾛的距离是： S=AB+BC
  
• 快指针⾛的距离是： 假设多⾛了n圈，2S = AB+(BC+CB)*n+BC ，
  

即 2(AB+BC) = AB+(BC+CB)*n+BC，也就是AB+BC = (BC+CB)*n
假设n =1 ，那么AB = CB ,也就是当前位置到环的⼊⼝的⻓度，等于链表头到环的⼊⼝的位置。
因此相遇之后，我们将⼀个快指针移动到链表头，两个指针每次⼀步，直到相遇，这个时候，相遇的节点就是环的⼊⼝节点。

1. public ListNode EntryNodeOfLoop(ListNode pHead) {
2.     ListNode quick = pHead;
3.     ListNode slow = pHead;
4.     while (quick != null && slow.next != null) {
5.         quick = quick.next;
6.         slow = slow.next.next;
7.         if (quick == slow) {
8.             quick = pHead;
9.             while (quick != slow) {
10.                 quick = quick.next;
11.                 slow = slow.next;
12.             }
13.             return quick;
14.         }
15.     }
16.     return null;
17. }

复制代码

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

标记法（破坏性解法）

通过修改节点结构来标记已访问的节点，适合可以修改链表的情况

1. public class Solution {
3.     public ListNode detectCycle(ListNode head) {
4.         if (head == null) return null;
5.         
6.         // 使用特殊值标记已访问节点
7.         final int MARKER = Integer.MIN_VALUE;
8.         ListNode current = head;
9.         
10.         while (current != null) {
11.             // 如果遇到标记值，说明是环的入口
12.             if (current.val == MARKER) {
13.                 // 恢复原始值（可选）
14.                 return current;
15.             }
16.             // 标记当前节点
17.             current.val = MARKER;
18.             current = current.next;
19.         }
20.         
21.         return null;
22.     }
23.    
24.     /**
25.      * 替代方案：使用额外字段进行标记（如果节点结构可扩展）
26.      */
27.     static class MarkableListNode {
28.         int val;
29.         MarkableListNode next;
30.         boolean visited;
31.         
32.         MarkableListNode(int val) {
33.             this.val = val;
34.             this.visited = false;
35.         }
36.     }
37. }

复制代码

• 时间复杂度：O(n) - 线性遍历
  
• 空间复杂度：O(1) - 但破坏了链表结构
  

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！