Sword finger offer II 022 Entry node of a link in a linked list

The finger of the sword Offer II 022. The entry node of a link in a list

difficulty ： secondary

Given a linked list , Return to the first node of the link where the list begins to enter . Start from the head node of the linked list next The first node where the pointer enters the ring is the entry node of the ring . If the list has no links , Then return to null.

To represent a ring in a given list , We use integers 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 It's just for identifying rings , It's not passed to the function as an argument .

explain ： It is not allowed to modify the given linked list .

Example 1：
Input ：head = [3,2,0,-4], pos = 1
Output ： The return index is 1 The linked list node of
explain ： There is a link in the list , Its tail is connected to the second node .

Example 2：
Input ：head = [1,2], pos = 0
Output ： The return index is 0 The linked list node of
explain ： There is a link in the list , Its tail is connected to the first node .

Example 3：
Input ：head = [1], pos = -1
Output ： return null
explain ： There are no links in the list .

Tips ：
The number of nodes in the list is in the range [0, 104] Inside
-105 <= Node.val <= 105
pos The value of is -1 Or a valid index in a linked list

1. Speed pointer

Ideas ： We use two pointers . 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 . Let the length of the outer part of the link in the linked list be a.slow After the pointer enters the ring , Gone again bb The distance between fast meet . here ,fast The pointer has gone through the ring n circle , So the total distance it has traveled is a+n(b+c)+b=a+(n+1)b+nca+n(b+c)+b=a+(n+1)b+nc. According to the meaning , Anytime ,fast The distance traveled by the pointer is slow Pointer 2 times . therefore , We have

a+(n+1)b+nc=2(a+b)*a=c+(n−1)(b+c)

With a=c+(n-1)(b+c)a=c+(n−1)(b+c) The equivalence of , 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 , Let's use an extra pointer ptr. start , It points to the head of the linked list ; And then , It and slow Move back one position at a time . Final , They will meet at the entry point .

The code is as follows

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

/** * @param {ListNode} head * @return {ListNode} */
var detectCycle = function(head) {
    
    let slow = head;
    let fast = head;
    while(fast != null && fast.next != null) {
    
        slow = slow.next;
        fast = fast.next.next;
        if(slow === fast) {
    
            //  Description ring 
            let ptr = head;
            while (ptr !== slow) {
    
                ptr = ptr.next;
                slow = slow.next;
            }
            return ptr;
        }
    }
    return null;
};

The time and space complexity are shown in the figure

2. Hashtable

Ideas ： Hash tables are easier to understand , Each node in the traversal linked list is stored in the hash table , If you traverse to a duplicate , That proves there is a ring ( Numerical repetition does not affect , namely 2 individual 2 or 3 individual 2 Will not interfere with the results , Because they val Same but next Different )

The code is as follows

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

/** * @param {ListNode} head * @return {ListNode} */
var detectCycle = function(head) {
    
    if(!head) return null;
    let set = new Set();
    let p = head;
    while(p) {
    
        if(set.has(p)) return p;
        set.add(p);
        p = p.next;
    }
    return null;

};

The time and space complexity are shown in the figure