(leetcode)环形链表Ⅱ-题解

题目描述

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

说明:不允许修改给定的链表。

进阶:你是否可以不用额外空间解决此题?

解题思路

最开始,我很自然地考虑遍历链表,并将当前节点在其后置子链表中查询,如果有相同的节点,则这个节点就是我们要找的入环点。但很明显,这种算法的时间复杂度是很高的。
下面引出的解法很类似高中物理中的追及问题。

我们直接来看演示图:
演示图

我们定义其中变量如下:

  • head:头节点
  • in:进入循环的节点
  • meet:快慢指针相遇的节点
  • L:环的长度
  • m:head到in的长度
  • n:meet到in的长度

我们定义两个指针:fastslow
fast指针每次走两格,slow指针每次走一格。
那么当两个指针相遇时,有 $$m+n+L=2 \times (m+n)$$ 这里我们考虑的是快慢指针只差一圈的情况,至于差得更远也只是这种情况的循环。此时解得:
$$L = m + n$$
即:$meet$到$in$的距离为$m$。于是,head与meet到in是等距的。
于是我们使得 $slow = in$和$fast = and$。当两个指针同时向前走,走到相等的位置就是环的入口了。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
public ListNode detectCycle(ListNode head) {
if(head == null || head.next == null || head.next.next == null)
return null; // 如果链表节点数小于3,显然不可能有环。
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast){
slow = head;
while(slow != fast){
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
return null;
}
}
凸包问题 (leetcode)连续整数求和-题解

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×