NC03
描述
给一个长度为n链表,若其中包含环,请找出该链表的环的入口结点,否则,返回null。
数据范围:
要求:空间复杂度 ,时间复杂度
示例1
输入:
{1,2},{3,4,5}
返回值:
3
说明:
返回环形链表入口节点,我们后台会打印该环形链表入口节点,即3
思路
使用NC03快慢指针
当链表无环时返回null
若链表有环 ,两指针在环内第一次相遇时,此时将slow指针指向头结点,然后fast和slow都走一步,直到再次相遇 此时的节点节点就是入环节点。
推导
如上图,是一个环形链表,设环外长度为a,指针slow进入环内后又走了长度b在q点和fast指针相遇
在相遇之前fast指针可能已经在环内走了n圈 故此时fast走过的距离为 a+n(b + c) + b
slow指针走过的距离为 a + b
又因为fast指针走过的距离为slow的二倍 故有 2(a + b ) = a + n(b + c) + b
化简上式得 a = (n - 1)(b + c ) + c
因为b + c 等于环长
所以上式的含义为链表头到入环节点p的距离等于从相遇点到入环节点的距离c 加上n-1被的环长
所以用c, h两个指针从p点和head开始走,当h走完A时,c走过的路为C + (n-1)(C+B),即n圈+C,所以h和c的相遇点为q
代码
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead) {
if (pHead == null && pHead.next == null) {
return null;
}
// 判断是否有环
ListNode slow = pHead;
ListNode fast = pHead;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
// 相遇
if (slow == fast) {
slow = pHead;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
return null;
}
}
Q.E.D.