转载

链表中环的入口节点

链表中环的入口节点

题目

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

思想

初始化两个指针fast, low, 开始都指向头结点, fast每下走两步, low每下走一步,如果

链表中有环,则两节点一定会相遇。如果没有环,则fast或者fast.next会先走到空

start: 头结点到相遇节点的距离

step: low指针在环中走过的距离

Distance(low) = start + step;

Distance(fast) = 2 * (start + step);

start + step = k * n(n为环的长度, k为正整数)

因为 start + step = k n, 故头结点,和low指针再走start步会在入口节点相遇
low指针走过的距离start+start + step,头指针走过的距离
*start,相差kn

代码

/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } */

public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        if(pHead == null) return null;
        ListNode fast = pHead;
        ListNode low = pHead;
        
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            low = low.next;
            
            if(fast == low) break;
        }
        
        if(fast == null || fast.next == null) return null;
        
        fast = pHead;
        while(fast != low) {
            fast = fast.next;
            low = low.next;
        }
        
        return fast;
    }
}
正文到此结束
本文目录