剑指Offer 56 链表中环的入口结点

题目描述

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

思路

1. hashset，最快的想法；重复检验嘛
2. 截断指针；因为什么呢？因为你会发现入口结点有两个入口，如果从头开始截断指针，最后的这个一定是入口结点；
3. 神奇的双指针：其实这个想法我稍微想过，不过步骤比较多，没想明白；首先我们进入了环中，就可以计算环的节点数目；第二个想法是在一个环中，两个结点追逐的话，在绕一圈以后，就会相遇；
   那对这一题来说：
   一个指针在头，另一个提前移动环节点数目，最后就会相遇；

   代码

   //hashset
    static public ListNode EntryNodeOfLoop(ListNode pHead)
       {
           if (pHead==null)
               return null;
           ListNode node = pHead;
           HashSet<ListNode> hashSet = new HashSet<>();
           while (pHead!=null)
           {
               if (hashSet.contains(node))
               {
                   return node;
               }
               hashSet.add(node);
               node = pHead.next;
               pHead= node;
   
           }
           return  null;
       }

//截断
    static public ListNode EntryNodeOfLoop1(ListNode pHead)
    {
        if (pHead==null||pHead.next == null)
            return  null;
        ListNode frontnode = pHead.next;
        ListNode backnode  = pHead;

        while (frontnode!=null)
        {
            backnode.next = null;
            backnode = frontnode;
            frontnode =frontnode.next;
        }
        return backnode;


    }

static public ListNode FindMeetingnode(ListNode pHead)
{
    if (pHead==null)
        return null;
    ListNode slow = pHead.next;
    if (slow!=null)
        return null;
    ListNode quick = slow.next;
    while (slow!=null&&quick!=null)
    {
        if (slow==quick)
            return  slow;
        slow = slow.next;
        quick = quick.next;

        if (slow != quick)
            quick=quick.next;
    }
    return null;
}
static public ListNode EntryNodeOfLoop2(ListNode pHead)
{
    ListNode meetingnode = FindMeetingnode(pHead);      //获取相遇节点
    if (meetingnode ==null)                             //相遇节点没有话，证明没有环
        return null;
    int nodesInloop = 1;                                //环节点数目
    ListNode p1 = meetingnode;
    while (p1.next!=meetingnode)                        //计算环节点数目
    {
        p1 = p1.next;
        ++nodesInloop;
    }
    p1 = pHead;
    for (int i = 0; i < nodesInloop; i++) {            //p1指针向前走环节点数目
        p1 =p1.next;
    }
    ListNode p2 = pHead;                                //p2指针为头结点
     while ( p1 !=p2)                                   //这时相遇时就是入口结点；
     {
         p1 =p1.next;
         p2 = p2.next;
     }
     return p1;
}

收获

1. 神奇的链表环，双指针；