剑指Offer 总结

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

public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {

        if(pHead == null) return null;

        ListNode f = pHead;

        ListNode s = pHead;

        //判断是否有环

        boolean hasLoop = false;

        while(s != null && f.next != null){

            f = f.next.next;

            s = s.next;

            if(f == s){

                hasLoop = true;

                break;

            }

        }

        if(!hasLoop) return null;

        //求得环的长度

        f = f.next.next;

        s = s.next;

        int length = 1;

        while(f != s){

            f = f.next.next;

            s = s.next;

            length++;

        }

        //找到环的入口

        f = s = pHead;

        for (int i = 0; i < length; i++)

            f = f.next;

        while (f != s){

            f = f.next;

            s = s.next;

        }

        return f;

    }

巴特西

剑指Offer 总结

最新文章

热门文章