Small knowledge, big challenge! This paper is participating in theEssentials for programmers”Creative activities

This is the force buckle series 6, today and friends together hit the card buckle 142: implementation of circular linked list II.

The title

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

To represent the rings in a given list, we use the integer pos to represent where in the list the tail joins (the index starts at 0). If pos is -1, there are no rings in the linked list. Note that pos is only used to identify the case of the ring and is not passed to the function as an argument.

Note: Modification of a given linked list is not allowed.

Advanced:

Can you use O(1) space to solve this problem?

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,2], pos = 0 output: returns a list node with index 0.Copy the code

Example 3:

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

Tip:

The number of nodes in the list is in the range [0, 104] -105 <= node. val <= 105 pos is -1 or a valid index in the list

Source: LeetCode link: leetcode-cn.com/problems/li… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Their thinking

This problem and the upgraded version of 141. Ring linked list, on the basis of the last problem, added a problem, is how to find the location of the node into the ring, we can still use the idea of fast and slow Pointers to solve this problem.

As shown in Example 1, we can define a fast pointer that takes two steps at a time and a slow pointer that takes one step at a time, and these two Pointers follow the following trajectory

1: Fast ->0 Slow ->2 2: fast ->2 Slow ->0 3: fast ->-4 Slow ->-4Copy the code

Here we go to the meeting point and we don’t go any further. Let’s look for the pattern. Here the fast pointer goes A+B and n loops, A+n(B+C)+B. The slow pointer goes A+B, and the fast pointer goes twice as far.

2(A+B) = A+n(B+C)+B
Copy the code

We can convert to A = n * C + (n-1) * B => A = (n-1) * (B + C) + C, and B + C is the length of A ring, which we ignore, so the final equation is

A = C

After obtaining this conclusion, we only need to find the intersection point, and then go down the position of the beginning node and the current slow pointer node to find the intersection point, which is the entrance of the ring.

Code implementation

/** * 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 pre = head;
    let cur = head;
    while (cur && cur.next) {
        pre = pre.next;
        cur = cur.next.next;
        if(pre === cur){
            let temp = head;
            while(temp! ==pre){ pre = pre.next; temp = temp.next; }returntemp; }}return null;
};
Copy the code

conclusion

The front end is long and long. We are all on the road. We hope to communicate with our friends and make progress together. Keep updating ing…..

Head over to the Leetcode column series to see more about unlocking.