LeetCode 142. Circular linked list II

Table of contents: Algorithm Diary

142. Circular Linked List II – Force Links (LeetCode) (leetcode-cn.com)

Topic describes

Given a linked 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). If pos is -1, there are no rings in the linked list. Note: POS is not passed as an argument, just to identify the actual state of the linked list.

Linked lists are not allowed to be modified.

Data range

• The number of nodes in the linked list is in the range [0 104][0, 10^4][0 104]
• 
  $-10^5 <= Node.val <= 10^5$
• posThe value of
  $– 1$Or a valid index in a linked list
• useO(1)Space complexity solves this problem

The subject sample

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

Algorithm ideas

Set two Pointers, blue for fast and yellow for slow. Blue, the fast pointer, took two steps at a time, and Yellow, the slow pointer, took one. ifThere is no ring, the fast pointer blue can certainly walk tonull. ifThere is ring, because each node in the ring has a unique edge, the fast pointer Blue and the slow pointer Yellow must meet at a point on the ring, and the meeting point is denoted asmeeting, the entrance to the ring is denoted asThe entrance.

Set the distance from the starting point to the entrance as XXX, then when yellow, the slow pointer, walks to the entrance, Blue, the fast pointer, has gone 2x2x2x. Remember that the position of blue, the fast pointer, is the marker point, then the distance from the entrance to the marker point is XXX. For the convenience of expression, set the distance from the entrance to the convergence point as YYY, then yellow, the slow pointer, takes YYy steps from the entrance to the convergence point, and Blue, the fast pointer, takes 2y2y2y steps from the marker point to the convergence point. Therefore, the distance from the marker point to the entrance is also YYy.

To sum up, the distance from the entrance to the marking point is
$x$, the distance between the mark point and the entrance is
$y$And the distance from the entrance to the rendezvous point is also
$y$, therefore, the distance from the junction point to the entrance is
$x$. So this tells us that the distance from the starting point to the entrance is the same as the distance from the junction point to the entranceequal.

According to the above proof, the convergence point is first found through the fast and slow Pointers, and then the two Pointers respectively start from the starting point and the convergence point at the same speed, and the intersection point is the entrance. Note the absence of rings.

AC code

/** * 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 == null || head.next == null) return null;
    let slow = head;
    let fast = head;
    while(fast ! =null) { 
        slow = slow.next;
        fast = fast.next;
        if(fast == null) return null;
        fast = fast.next;
        if(slow == fast) { // find the point of convergence
            slow = head;
            while(slow ! = fast) { slow = slow.next; fast = fast.next; }returnslow; }}return fast;
};
Copy the code