[每日一道小算法(五十三)] [链表]链表环的入口结点(剑指offer)
程序员文章站
2022-06-17 16:15:32
...
前言:
以前做过链表是否有环的判断题,这道题是要求入口结点,着实想了好久。
题目描述
给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。
解题思路
判断有环的话,我们可以使用两个指针来完成,快慢指针。慢指针每次走一步,快指针每次走两步,如果有环,则一定会相遇。这个方法是用来判断链表是否有环,那么如何找到入口结点呢。
我接着分析。我们找到快慢指针相遇的点p。我们假设环的入口结点在点q,从头结点到点q距离为A,q p 两点距离为B,p q 两点距离为C。因为快指针是慢指针的两倍速,且他们在p点相遇,则我们可以得到等式2(a+b) = a + b + c + b。根据这个等式,我们可以得出c = a。此时我们的slow指针继续保持原来的走法,新建一个slow2指针从头开始走。每次都走一个。这样当这两个指针相遇时,就是入口结点。因为a = c。不懂得结合下面的图,看一下就会明白了。
其实就是我们直到这个环有n个结点,让两个指针从开始走,p1先走n个结点,然后两个指针同时开始走,当他们相遇时那个结点就是入口结点。
代码样例
package com.asong.leetcode.EntryNodeOfLoopLsit;
/**
* 链表环的入口结点
* 给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。
*/
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead)
{
if(pHead==null)
{
return null;
}
//快慢指针 快指针走两步 慢指针走一步 如果
//快指针到达尾结点了,则无环,否则快慢指针相等则代表链表有环
ListNode low = pHead;
ListNode high = pHead;
while(high!=null && high.next!=null)
{
low = low.next;
high = high.next.next;
if(low == high)
{
//如果有环
ListNode slow2 = pHead;
while(slow2!=low){
slow2 = slow2.next;
low = low.next;
}
return slow2;
}
}
return null;
}
}