欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[每日一道小算法(五十三)] [链表]链表环的入口结点(剑指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。不懂得结合下面的图,看一下就会明白了。
[每日一道小算法(五十三)] [链表]链表环的入口结点(剑指offer)
其实就是我们直到这个环有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;
    }
}