本文主要是介绍【力扣】203、环形链表 II,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
142. 环形链表 II
要解决这道题,首先需要对问题进行拆解:
- 确定链表是否存在环
- 确定环的入口点
如何判断是否存在环呢?这个比较容易想到,使用快慢指针即可判断链表是否存在环。我们定义两个指针:
ListNode slow = head;
ListNode fast = head;
让 fast 指针的移动速度是 slow 指针的两倍即可,当它们再次相遇时,说明 fast 指针比 slow 指针多走了一圈,并重新追上 slow 指针了,此时可以说明链表存在环。
while(fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;// 如果慢指针追上快指针,说明存在环if(slow == fast) {...}
}
return null;
如何确定环的入口点呢?这涉及到数学推导,这一步不太容易想到:
让我们假设三个变量 x,y,z
可以得到公式如下:
slow指针走过的距离 * 2 = fast指针走过的距离
于是得到等式如下:
2(x + y) = (x + y) + n(y + z) // n(y+z)表示fast指针绕环的长度
x + y = n(y + z)
x = nz + (n - 1)y
x = (n - 1)(z + y) + z
因此我们可以知道,在 slow 指针和 fast 指针相遇的节点处,满足该等式:x = (n - 1)(z + y) + z
这个式子表示什么呢?表示一个指针从头节点处出发,到环型入口处经过的距离 x 等于另一个指针从 slow 和 fast 相交的节点处出发,经过 z + (n - 1)(z + y),即走过 z 距离并绕环 n-1 圈,至于这个 n 是多少我们不必知道,于是可以得到以下代码:
// 通过数学规律发现,相交的节点到环的入口处的节点数等于头节点到环入口处的节点数
ListNode temp = head;
// 如果存在环,必定不会死循环
while(temp != slow) {temp = temp.next;slow = slow.next;
}
return slow;
至此,题解,完整 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 slow = head;ListNode fast = head;while(fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;// 如果慢指针追上快指针,说明存在环if(slow == fast) {// 通过数学规律发现,相交的节点到环的入口处的节点数等于头节点到环入口处的节点数ListNode temp = head;// 如果存在环,必定不会死循环while(temp != slow) {temp = temp.next;slow = slow.next;}return slow;}}return null;}
}
这篇关于【力扣】203、环形链表 II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!