剑指Offer-链表环入口节点

标签: 算法基础  剑指offer系列

剑指offer——链表中环入口节点

题目:给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。

解题思路:通过设置两个指针,快慢指针,其中快指针每次走两步,满指针每次走一步
草图如下:
这里写图片描述
其中从开始到环的入口长度为x,假设在环(环长度为n)上的B点相遇,设环入口到B点为a,则B到A(顺时针)为n-a
有次可推出:
快指针走过的长度: x+n*K+a(其中K表示走过K圈个环)
慢指针走过的长度为:x+n*L+a(其中L意思同上)
由于快指针是满指针的速度2倍则有
x+n*K+a=2*(x+n*L+a)
=>x=(K-2L)*n-a
=>x=(K-2L-1)*n +(n-a) (K-2L-1可以表示0或者多个环的长度)
由此可让慢指针在B点开始,快指针从链表开始步长均为1进行遍历,当两个指针相遇时则相遇地点就是环的入口

class Solution
{
    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        // write code here
       //若只有头结点返回null
        if(pHead.next==null)
            return null;
         //通过设置快慢指针
        ListNode fast=pHead;
        ListNode slow=pHead;        
        while(fast!=null)
        {
            //快指针步长为2
            fast=fast.next.next;
            //慢指针步长为1
            slow=slow.next;
            //若快慢指针相遇
            if(fast==slow)
            {
                //重置快指针,并将其步长设为1
                 fast=pHead;   
                //两指针再次相遇,说明在环的入口
                 while(fast!=slow)
                 {
                     fast=fast.next;
                     slow=slow.next;
                 }
                return fast;
            }           
        }
         return null;                           
    }
}
原文链接:加载失败,请重新获取