力扣142.环形链表II & 剑指offer 55. 链表中环的入口结点

142. 环形链表 II & 剑指offer 55. 链表中环的入口结点

题目描述

给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null

法一:

思路转自:23. 链表中环的入口结点

使用双指针,一个快指针 fast 每次移动两个节点,一个慢指针 slow 每次移动一个节点。因为存在环,所以两个指针必定相遇在环中的某个节点上。

假设环长为 L,从起点 x1 到环的入口的步数是 x,从环的入口y1继续走 y 步到达相遇位置z1,从相遇位置继续走 z 步回到环的入口y1,则有 y+z=L

假设快指针 fast 在圈内绕了 N 圈,则总路径长度为 x+y+N(y+z)。表示快指针到达z1相遇点后还多走了 N 圈,后面就不需要再走了。

而慢指针 slow 总路径长度为 x+y + m(y+z),表示慢指针到达z1相遇点后还多走了 m 圈。

因为快指针是慢指针的两倍,因此 x+y+N(y+z) = 2(x+y+m(y+z))。

我们要找的是环入口节点 y1,也可以看成寻找长度 x 的值,因此我们先将上面的等值分解为和 x 有关:x=(N-2m)(y+z) - y。

上面的等值没有很强的规律,但是我们可以发现 y+z 就是圆环的总长度,因此我们将上面的等式再分解:x=(N-2m-1)(y+z)+z = (N-2m-1)L + z。这个等式左边是从起点x1 到环入口节点 y1 的长度,而右边是在圆环中走过(N-2m-1)圈,再从相遇点 z1 再走过长度为 z 的长度。所以我们可以发现慢指针在 z1 处在向前走 z 步后会到达入环结点处,继续走(N-2m-1) 圈仍然是处于这个入环结点处,所以慢指针 z1 位置向前走 (N-2)(y+z) + z 步后会到达入环结点,而 (N-2m-1)(y+z)+z 刚好等于 x, 即等于起点到入环结点的距离,所以此时我们如果让两个指针分别从起点 x1 和相遇点 z1 开始向前走,每次只走过一个距离,那么最后他们会在环入口节点相遇。

快慢指针,快指针一次走两步,慢指针一次走一步,相遇后,快指针回到头结点,以一次一步的速度和慢指针一起走,再次相遇的结点即是环的入口点

 1 public class Solution {
 2     public ListNode detectCycle(ListNode head) {
 3         ListNode fast = head, slow = head;      // 定义快慢指针
 4         while(true){
 5             if(fast == null || fast.next == null){
 6                 return null;
 7             }
 8             slow = slow.next;
 9             fast = fast.next.next;
10             if(slow == fast){       // 相遇结点退出循环
11                 break;
12             }
13         }
14 
15         fast = head;
16         while(slow != fast){
17             fast = fast.next;
18             slow = slow.next;
19         }
20         return fast;
21     }
22 }

力扣测试时间为0ms, 空间为39.7MB

复杂度分析:

时间复杂度:我们根据慢指针所走过的路程来作为时间复杂度的估计,假设从链表头结点到入环结点的结点个数为N1, 环的结点的个数为L,时间一共分为三部分,第一部分是遍历前N1个结点的时间,第二部分是慢指针从入环到与快指针相遇花费的时间,第三部分是相遇后将快指针拉回到链表表头,快慢指针再次相遇所花费的时间,第一部分和第三部分慢指针经过的结点个数都是N1,所以时间都是O(N1),下面讨论慢指针在入环直至与快指针相遇所花费的时间。

根据环形跑道相向的追及问题,如果两个跑步者从同一起点出发,如果两者速度不同那一定会相遇。第一次相遇肯定是速度快着比速度慢者多跑了一圈,当两人相遇时距离他们下次相遇所花费的时间是最大的(假设花费的时间为t),其他情况下距离他们的下次相遇时间都小于这个最大值,所以从现在开始到相遇,速度快者比速度慢者多跑的距离肯定小于一圈。

慢指针入环后,此时快指针已经在环上了,所以距离他们的下次相遇时间肯定小于等于t,所以从现在开始到相遇,快指针比慢指针多跑的距离肯定小于一圈,假设慢指针的速度为v,指针的速度为kv, 那么kvt - vt <= L,  所以 vt<= L/(k-1), 又因为 k = 2, 所以 vt <= L, vt刚好是慢指针在环上经过的结点个数,所以慢指针入环后最多经过 L 个结点就会被快指针追上,所以慢指针从入环到相遇所花费的时间最大为O(L),所以总的时间为O(t) <= 2*O(N1)+O(L)

所以时间复杂度为O(N)

空间复杂度:O(1)

下面这种写法是错误的,要注意

 1 public class Solution {
 2     public ListNode detectCycle(ListNode head) {
 3         if(head == null || head.next == null){
 4             return null;
 5         }
 6 
 7         // 下面fast = head.next 导致在相遇结点处快指针走过的结点个数不是慢指针的两倍,
 8         // 而是慢指针的两倍加一,所以不能用上面的推导公式
 9         ListNode slow = head, fast = head.next; 
10         // 找到第一个相遇的结点
11         while(slow != fast){
12             if(fast == null || fast.next == null){
13                 return null;        // 如果没有环,直接退出
14             }
15             slow = slow.next;       // 更新两个结点的位置
16             fast = fast.next.next;   // fast每次移动两个结点
17         }
18 
19         fast = head;
20         while(slow != fast){
21             fast = fast.next;
22             slow = slow.next;
23         }
24         return fast;
25     }
26 }

 上面这段程序看似和第一个程序一样,只是快指针的起点不一样,但是都会在快慢指针相遇后跳出循环,然后把快指针拉回到起点后再次寻找相遇点,但是第二段程序就是会超时,原因是第二段程序的 fast的初值为fast = head.next 导致在相遇结点处快指针走过的结点个数不是慢指针的两倍,而是慢指针的两倍加一,所以不能用上面的推导公式,不能直接把快指针拉回到链表表头,这里我也不知道应该把链表拉回到链表的哪个位置QAQ。

法二:

思路:把所有结点存入一个 ArrayList 中,第一个重复的结点就是入口结点,如果没有重复结点,则无环

 1 import java.util.ArrayList;
 2 public class Solution {
 3 
 4     public ListNode EntryNodeOfLoop(ListNode pHead)
 5     {
 6         // 如果链表只有一个结点或者没有结点则直接返回空
 7         if(pHead == null)
 8             return null;
 9         ArrayList<ListNode> list = new ArrayList<ListNode>();
10         list.add(pHead);
11         ListNode p = pHead.next;
12         while(p != null){
13             if(list.contains(p)){
14                 return p;
15             }
16             list.add(p);
17             p = p.next;
18             
19         }
20         return null;
21     }
22 }

 复杂度分析:

时间复杂度:O(n)

空间复杂度:O(n)

原文地址:https://www.cnblogs.com/hi3254014978/p/12416446.html