链表的入环结点

比眉伴天荒 2024-04-18 14:42 50阅读 0赞

## 题目描述 ##

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

## 分析： ##

> 以下为分析过程为 左程云 《程序员代码面试指南 --IT名企算法与数据结构题目最优解》中的解析

> 如果一个链表没有环，那么遍历链表一定可以遇到链表的终点；如果链表中有环，那么遍历链表就永远在环里转下去了。如何找到第一个入环结点，具体过程如下：
> 
> 1.  设置一个慢指针 slow 和一个快指针 fast 。在开始时， slow 和 fast 都指向链表的头结点 head, 然后 slow 每次移动一步，fast 每次移动两步，在链表中遍历。
> 2.  如果链表无环，那么fast 指针在移动过程中一定先遇到终点，一旦 fast 到达终点，说明链表中是 没有环的，直接返回 null ，表示链表无环，当然也没有第一个入环的结点。
> 3.  如果链表有环，那么 fast 指针和 slow 指针一定会在环中的某个位置相遇， 当 fast 和 slow 相遇时， fast 指针重新回到 head 的位置，slow 指正不懂。接下来，fast 指针从每次移动两步改为每次移动一步，slow 指针依然每次移动一步，然后继续遍历。
> 4.  fast 指针和 slow 指针一定会再次相遇，并且在第一次入环的节点处相遇。

## 代码 ##

public ListNode EntryNodeOfLoop(ListNode pHead){     
            if(pHead == null || pHead.next == null || pHead.next.next == null){ 
                return null;
            }
            ListNode s = pHead.next;
            ListNode f = pHead.next.next;
            while(s != f){ 
                if(f.next == null || f.next.next == null){ 
                    return null;
                }
                s = s.next;
                f = f.next.next;
            }
            f = pHead;
            while(s != f){ 
                f = f.next;
                s = s.next;
            }
            return s;
        }