Location>code7788 >text

[Ninja Algorithm] From the entry point to the encounter point: In-depth understanding of the ring-linked list II｜LeetCode Question 142 Ringed list II

Popularity：871 ℃/2025-02-18 23:51:11

[Ninja Algorithm] From the entry point to the encounter point: In-depth understanding of the ring link list II｜LeetCode Question 142

Problem escalating: Not only do you need to find a ring, but you also need to find a ring point

In the previous question, we discussed how to determine whether a linked list has a loop. Now let's go a step further: If we are sure there is a ring in the linked list, how should we find the entry node of the ring? It's like on an annular track not only to confirm that the runway is annular, but also to find the starting point of the annular track.

Problem description

LeetCode Question 142 "Ring Link List II" requirements: Given the head of a linked list, return the first node where the linked list starts to enter the ring. If the linked list is not ringed, null is returned.

For example:

Enter: 3 → 2 → 0 → -4
          ↑________________|
 Output: Return Node 2
 Explanation: There is a ring in the linked list, and its tail is connected to the second node

Start with the meeting of fast and slow pointers

Do you still remember the fast and slow pointers encountered in the previous question? That encounter point seems random, but actually contains important mathematical principles. Let's use this encounter point to find the entry point.

Clever mathematical relationship

Assumptions:

  • The distance from the link header to the entry point is a
  • The distance from the entry point to the encounter point is b
  • The distance from the encounter point to the entry point is c

When the fast and slow pointers meet:

  1. The distance traveled by the slow pointer: a + b
  2. The distance traveled by the fast pointer: a + b + n(b + c), where n is the number of circles the fast pointer walks in the ring
  3. Because the fast pointer is twice as fast as the slow pointer, so: 2(a + b) = a + b + n(b + c)

By solving this equation, we find that: a = c + (n-1)(b + c)
This means: starting from the head of the linked list and the encounter point at the same time, you will eventually meet at the entry point!

Code implementation

public ListNode detectCycle(ListNode head) {
     // Handle special circumstances
     if (head == null || == null) {
         return null;
     }
    
     // Stage 1: Use the fast and slow pointer to find the encounter point
     ListNode slow = head;
     ListNode fast = head;
     ListNode interference = null;
    
     while (fast != null && != null) {
         slow = ;
         fast = ;
         if (slow == fast) {
             intersection = slow;
             break;
         }
     }
    
     // If there is no encounter point, it means there is no ring
     if (intersection == null) {
         return null;
     }
    
     // The second stage: start from the beginning node and the encounter point at the same time, and find the ring point
     ListNode start = head;
     while (start != intersection) {
         start = ;
         intersection = ;
     }
    
     return start;
 }

Graphical process

1) Initial status:
 3 → 2 → 0 → 4
     ↑________________|
 S,F

 2) Fast and slow pointers meet:
 3 → 2 → 0 → 4
     ↑________________|
         S,F

 3) Start from the beginning and the encounter point at the same time:
 3 → 2 → 0 → 4
     ↑________________|
 P1 P2

 4) Encounter at the entry point:
 3 → 2 → 0 → 4
     ↑________________|
     P1, P2

Relationship with the previous question and advancement

Compared with the circular linked list I, this question is a natural advancement:

  1. Both questions use fast and slow pointer techniques
  2. This question reuses the process of finding the encounter point in the previous question
  3. After finding the encounter point, the steps to find the entry point are added

Implement details and optimization

  1. Space complexity remains O(1)
  2. Time complexity is O(n)
  3. No additional data structure required
  4. Code is elegant and intuitive

Thinking and Extension

This question tells us:

  1. Sometimes the solution to the problem is hidden in the characteristics of the problem itself
  2. Mathematical relationships can help us find elegant solutions
  3. Fast and slow pointers can not only detect rings, but also help us find key nodes

Thinking about practical application

The idea of ​​this algorithm can be applied in many practical scenarios:

  1. Detect cyclic dependencies
  2. Deadlock detection
  3. Processing of circular references

Let's remember: When we encounter similar "finding special points" problems, we can try to use the path features to find elegant solutions.

Author: Ninja Algorithm
Official account: Ninja Algorithm

I have prepared a list of questions to practice and detailed questions for these questions, covering most common interview questions. I can say responsibly that as long as you truly master these questions, 80% of the algorithm interviews will encounter similar questions. Reply to the official account [Question List] to obtain ~

<Previous Next>