LeetCode 142. Circular linked list II

Title Description ： Given the head node of a linked list head , Return to the first node of the link where the list begins to enter . If the list has no links , Then return to null.

If there is a node in the linked list , It can be done by continuously tracking next The pointer reaches again , Then there is a ring in the linked list . To represent a ring in a given list , The evaluation system uses an integer pos To indicate where the end of the list is connected to the list （ Index from 0 Start ）. If pos yes -1, There are no links in the list . Be careful ：pos Not passed as an argument , Just to identify the actual situation of the linked list . No modification allowed Linked list .



Method 1 ： Use map aggregate

A very intuitive idea is ： Make a statement map aggregate (key： node , value： Record the node location ), Then traverse each node in the linked list , Judge whether the node is located in map Collection , If it does not exist, add the node to map Collection , If there is , This indicates that there are links in the linked list , Return to the node .

   /** *  Use map aggregate  * @param head * @return */
    public static ListNode detectCycle(ListNode head){
    
        if(head == null || head.next == null){
    
            return null;
        }

        Map<ListNode, Integer> map = new HashMap<>();
        int pos = 0;  //  The initial index is 0
        while (head != null){
    
            if(map.containsKey(head)){
    
                return head;
            }
            map.put(head, pos++);
            head = head.next;
        }

        // head == null Jump out of while loop , The linked list does not contain chains 
        return null;

    }

Method 2 ： Speed pointer

We use two pointers ,fast And slow. They all start at the head of the linked list . And then ,slow The pointer moves back one position at a time , and fast The pointer moves back two positions . If there are rings in the list , be fast The pointer will end up with slow The pointer meets in the ring .

As shown in the figure below , Let the length of the outer part of the link in the linked list be x.slow After the pointer enters the ring , Gone again y The distance between fast meet . here ,fast The pointer has gone through the ring n circle , So the total distance it has traveled is $x+n(y+z)+y=x+(n+1)y+z.$

According to the meaning , Anytime ,fast The distance traveled by the pointer is slow Pointer 2 times . therefore , We have $$x+(n+1)y+z=2(x+y)*x=z+(n-1)(y+z)$$

With this equivalence , We will find that ： The distance from the meeting point to the entry point plus n−1 Ring length of circle , Exactly equal to the distance from the head of the linked list to the ring entry point .

therefore , If I found slow And fast When we met , We'll use two extra pointers index1, index2. start , They point to the head of the linked list and slow And fast Point where the pointer meets ; And then ,index1 and index2 Move back one position at a time . Final , They will meet at the entry point .

 /** *  Think fast and slow  * @param head * @return */
    public static ListNode detectCycle(ListNode head){
    
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null){
    
            slow = slow.next;  // slow One step at a time 
            fast = fast.next.next; // fast Take two steps at a time 

            if(fast == slow){
      //  Ring 
                ListNode index1 = fast;
                ListNode index2 = head;
                //  Two pointers ,  Ab initio node and encounter node , Take one step each , Until we met , The meeting point is the entrance of the ring 
                while (index1 != index2){
    
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            }
        }
        return null;

    }

Think about the problem 1： In the case of rings , Why the slow pointer must meet the fast pointer ?

• It can be considered that the fast pointer and the slow pointer move relatively , Suppose the speed of the slow pointer is 1 node / second , The speed of the fast pointer is 2 node / second , When taking the slow pointer as the reference system （ That is, the slow pointer is still ）, The movement speed of the fast pointer is 1 node / second , So I'm sure we'll meet .

Think about the problem 2： Why do we meet on the first lap ？

• Let the length of the ring be L, When the slow pointer just enters the ring , The slow pointer needs to go L Step ( namely L second ) To finish a lap , At this time, the maximum distance between the fast pointer and the slow pointer is L-1, Once again, we take the slow pointer as the reference frame , As mentioned above , Come on, the pointer is following 1 node / The speed of seconds is catching up with the slow pointer , So it must be in L Catch up with the slow pointer in seconds .