剑指Offer：链表中环的入口节点【23】

题目描述

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

题目分析

　　第一步确定链表中是否包含环，怎么确定呢？我们定义两个指针橙和蓝，橙每次走一步，蓝每次走两步，如果他俩重合了，这就说明链表中存在环。

　　

　　第二步求环的长度，两者碰头后，让其中一个继续走，每走一步步数加一，然后求得环的长度。

　　第三步求环的初始节点，仍然是两个指针，其中一个事先走环长个节点，然后两者同时移动，直到两者碰头，然后那个节点就是环的初始节点。

　　

Java题解

public static ListNode EntryNodeOfLoop(ListNode pHead)

    {

        //确定是否有环

        if(isCircle(pHead))

        {

            //求环的长度

            int len =getLenOfCircle(pHead);

            ListNode pA = pHead;

            ListNode pB = pHead;

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

            {

                pB=pB.next;

            }

            while (pA.val!=pB.val)

            {

                pA=pA.next;

                pB=pB.next;

            }

            return pA;

        }

        return null;

    }

    //确定是否有环

    public static boolean isCircle(ListNode pHead)

    {

        try {

            ListNode pA = pHead.next;

            ListNode pB = pHead.next.next;

            while (pA != null && pB != null && pA.val != pB.val) {

                pA = pA.next;

                pB = pB.next.next;

            }

            return true;

        }catch (Exception e)

        {

            return false;

        }

    }

    //求环的长度

    public static int getLenOfCircle(ListNode pHead)

    {

        ListNode pA = pHead.next;

        ListNode pB = pHead.next.next;

        while (pA != null && pB != null && pA.val != pB.val) {

            pA = pA.next;

            pB = pB.next.next;

        }

        int length = 1;

        while (pB.next.val!=pA.val)

        {

            pB=pB.next;

            length++;

        }

        return length;

    }

巧妙的方法

import java.util.*;

public class Solution {

 

    public ListNode EntryNodeOfLoop(ListNode pHead)

    {

        if(pHead==null)

            return null;

        ListNode pNode=pHead;

        HashSet<ListNode> pSet = new HashSet<ListNode>();

        while(pNode!=null){

            if(!pSet.add(pNode))

                return pNode;

            pNode=pNode.next;

        }

        return null;

    }

}