Circular linked list

Circular linked list

The title

Given a linked list, determine whether there are rings in the list.

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, 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: POS is not passed as an argument, just to identify the actual state of the linked list.

Returns true if there are rings in the list. Otherwise, return false.

Example:

Input: head = [3,2,0,-4], pos = 1 output: true explanation: there is a ring in the linked list whose tail is connected to a second node.Copy the code

Train of thought

Use the fast or slow pointer:

1. Initialize the fast or slow pointer firstfast,slowPointing to the head node
2. The fast pointer takes two steps at a time and the slow pointer takes one step at a time
3. If the linked list is looped, the fast and slow Pointers will eventually point to the same node
4. If the list is not looped, the fast pointer goes to the end of the list first

code

function hasCycle(head) {
  // Initialize the fast or slow pointer
  let fast = slow =  head;
  while(fast ! = =null&& fast.next ! = =null) {// Lists may have an odd number of nodes or even numbers of nodes
    // The slow pointer moves one step at a time
    slow = slow.next;
    // The fast pointer takes two steps at a time
    fast = fast.next.next;
    // If the ring must meet
    if(slow === fast) return true;
  }
  // If the fast Pointers do not meet at the end of the list, they are not looped
  return false;
};
Copy the code

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.

Example:

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

Train of thought

According to the above two-pointer method, we can know where the meeting point of the ring linked list is. At this point, the fast pointer (or slow pointer) is set to point to the starting node (head node) of the ring linked list at the meeting point, and then the fast and slow Pointers are set to continue walking at the same pace. Then the point where the fast and slow Pointers meet again is the starting point of the ring.

Why is this correct?

👭 Friendly warning: the following proof will involve some mathematics, which may be a bit convoluted, but it should be easy to understand after careful reading and careful thinking

$Proof as follows \Downarrow$

---

The fast and slow hands start from the head of the circular chain and make the fast hands walk 222 steps per second and the slow hands walk 111 steps per second. It takes XXX seconds for the fast and slow hands to reach the meeting point.

So at the meeting point, the fast pointer took 2x2x2x steps and the slow pointer took XXX steps. It is assumed that the number of turns of the fast pointer is MMM and that of the slow pointer is NNN. So in this case, for fast Pointers we have the following equation

For slow Pointers we have the following equation

Make (2) ∗ 2 – (1) (2) * 2 – (1) (2) ∗ 2 – (1) to 0 = n – m (2) ∗ S + Y + L0 = (2 n – m) * S + Y + L0 = n – m (2) ∗ S + Y + L, L = (m – 2 n) ∗ S – YL = (m, 2 n) * S – YL = (m – 2 n) ∗ S – Y. As L⩾0L\geqslant 0L⩾0, the value of M −2nm-2nm−2n = = 1\geqslant 1⩾1 is an integer, L=(m−2n−1)∗S+S−YL=(M-2n-1)*S+ S-yl =(M − 2n-1) ∗S+S−Y. P =m−2n−1p= M-2n-1p = M −2n−1, where L=p∗S+S−YL= P *S+ S-yl =p∗S+S−Y, where P ⩾0p\geqslant 0p⩾0 = M −2n−1.

Because the fast pointer points to the head node of the circular list when they meet, the fast and slow Pointers continue at the same pace. When the fast pointer reaches the starting point of the loop, it takes LLL steps, and since L=p∗S+S−YL= P *S+ S-yl =p∗S+S−Y, the fast pointer takes P ∗S+S−Yp*S+ S-yp ∗S+S−Y. Since fast and slow Pointers move at the same pace, that is, the slow Pointers also take P ∗S+S−Yp*S+ S-yp ∗S+S−Y steps from the point where they meet, At this point, we only need to prove that the slow Pointers take P ∗S+S−Yp*S+ S-yp ∗S+S−Y steps from the encounter and stop at the starting point of the ring exactly to prove that the above idea is correct. However, the clockwise distance from the encounter point to the starting point of the ring is exactly S−YS-YS−Y steps, so the P ∗S+S−Yp*S+ S-yp ∗S+S−Y steps taken by the slow pointer can be described in words as follows: The slow pointer first takes S−YS-YS−Y steps from the point of encounter to the starting point of the ring, and then moves clockwise through the PPP circle at the starting point of the ring, that is, P ∗Sp*Sp∗S steps, and finally returns to the starting point of the ring and meets the fast pointer.

---

$Prove \quad \Uparrow$

code

// If a list is looped, return the starting node of the loop
function detectCycle(head) {
  // Initialize fast and slow Pointers to the head node
  let slow = head;
  let fast = head;
  while(fast ! = =null&& fast.next ! = =null) {
    // The slow pointer moves forward each time
    slow = slow.next;
    // The fast pointer advances two steps at a time
    fast = fast.next.next;
    // If there is a loop, the fast and slow Pointers must meet and exit the current while loop
    if (slow === fast) break;
  }
  // Redirect the fast pointer to the head node
  fast = head;
  while(true) {// Let the fast and slow Pointers move at the same pace
    slow = slow.next;
    fast = fast.next;
    // The point where the fast and slow Pointers meet is the starting node of the ring
    if(slow === fast) returnslow; }}Copy the code

Afterword.

There are two difficulties in this article (circular linked list) :

• First: how to think of useHow fast a pointerWhat about circular lists?
  • Multiple brush bai
• Second: How to proveHow fast a pointerIs the train of thought right?
  • Some mathematical reasoning skills are required

The article is mainly used for the peacetime review consolidation and accumulation, if there are writing mistakes in the place also hope you big guy give advice 🙏.

The resources

• LeetCode Link – Circular linked list
• LeetCode Links – Circular linked List II
• Front-end algorithm system exercise: end of linked list