“This is the 24th day of my participation in the First Challenge 2022. For details: First Challenge 2022.”

The title

Given the head node of a list, return the first node where the list begins to loop. Returns NULL if the list is loopless.

If there is a node in the list that can be reached again by following the next pointer continuously, then there is a ring in the list. To represent the rings in a given list, the metric system internally uses the integer POS to represent where the tail of the list is connected to in the list (the index starts at 0). Note: pos is not passed as an argument. Just to identify the reality of linked lists.

Linked lists are not allowed to be modified.

Example 1

Input: head = [3,2,0,-4], pos = 1 output: returns the list node with index 1.Copy the code

Example 2

Input: head = [1], pos = -1 Output: returns NULL Explanation: There are no loops in the linked list.Copy the code

Train of thought

LeetCode 👉 HOT 100 👉 The first node in a linked list is node 2. The first node in a linked list is node 2.

If there are rings in the linked list, the entry point is the first repeated element encountered when the list is traversed. As in the previous article, you can use the Set structure to store visited nodes and simply return the first repeated node

    /** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /

    / * * *@param {ListNode} head
     * @return {ListNode}* /
    var detectCycle = function(head) {
        const set = new Set(a);while (head) {
            // returns the first node of the repeat
            if(set.has(head)) {
                return head;
            } else{ set.add(head); head = head.next; }}return null;
    };
Copy the code

The above solution, the problem is still too high in space complexity, O(n); The solution method on the official website of LeetCode uses three Pointers slow, FAST and PTR, and uses mathematical formulas to derive the node that enters the loop. If you are interested, you can take a look for yourself, portal ☞

Here is another way to think about it. If there are rings in the list and len is the length of the ring, then len is the entry point for the penultimate node

The specific steps are as follows:

  • Two Pointers slow and fast are used to judge whether the ring exists. When the ring exists, when the two Pointers meet, save the meeting node as meetNode, which must be in the ring. If the ring does not exist, null is returned

  • Initialize Len = 0 to let meetNode continue traversing the ring, with Len ++ for each traversal. MeetNode == fast is the end condition, where Len is the length of the ring.

  • Use slow and fast again to initialize the head node head and let the fast pointer take len steps first. When fast. Next == slow, it indicates that FAST has reached the last node. At this point, the slow pointer points to the entry point.

    / * * *@param {ListNode} head
     * @return {ListNode}* /
    var detectCycle = function(head) {
        if(! head)return null;
        
        // Check if there is a ring
        let slow = head, fast = head.next;
        while(slow ! = fast) {if(! fast || ! fast.next) {return null;
            }

            slow = slow.next;
            fast = fast.next.next;
        }

        // Calculate the length of the ring
        let len = 0, meetNode = fast;
        while(meetNode.next ! = fast) { meetNode = meetNode.next; len++; }// reinitialize the fast or slow pointer
        slow = head, fast = head;

        // The fast pointer goes first
        while(len > 0) {
            fast = fast.next;
            len--;
        }

        // When fast reaches the tail, next equals slow
        while(slow = ! fast.next) { slow = slow.next; fast = fast.next; }// The current slow is the entry point
        return slow;
    };
Copy the code

summary

If you really don’t have ideas, draw a picture, often in the drawing process, will leak out.

For linked list operations, double Pointers, often come in handy

LeetCode 👉 HOT 100 👉 Circular linked list II – Medium problem ✅

Collection: LeetCode 👉 HOT 100, will update when you are free, we support a lot, click a like 👍

If you have a good solution or find something wrong with this article, please leave a comment at 😄