剑指offer:链表中环的入口结点

xiaoxiao2021-02-28  103

题目:一个链表中包含环,请找出该链表的环的入口结点。

判断一个链表是否有环,可以用快慢指针来判断,开始的时候快慢指针都指向头结点,慢指针一次走一个,快指针一次走两个,当他们相遇的时候说明此链表有环,并且相遇的结点一定是在环中。可以从这个结点出发,一遍继续向前移动一边计数,当再次回到这个结点的时候,就能得到环中的结点数了。其实就像操场跑圈一样,跑得快的和跑的慢的人相遇,跑得快的要不是比慢的多跑一圈要么多跑n圈。当确定链表有环以后,可以将慢指针从头指针开始,快指针还在相遇的位置开始,快慢指针每次都向前移动一个,再次相遇的时候就是环的入口结点。

代码如下:

public class Solution {     public ListNode EntryNodeOfLoop(ListNode pHead)     {         if(pHead==null||pHead.next==null)             return null;         ListNode faster=pHead;         ListNode slow=pHead;         while(faster!=null&&faster.next!=null){             slow=slow.next;             faster=faster.next.next;                  if(slow==faster){             slow=pHead;                  while(slow!=faster){             slow=slow.next;             faster=faster.next;         }         if(slow==faster)             return slow;         }     }       return null;       } }

转载请注明原文地址: https://www.6miu.com/read-26304.html

最新回复(0)