Location>code7788 >text

[Ninja Algorithm] From fast and slow pointer to countdown search: Elegantly solve the problem of countdown of linked list | LeetCode Question 19 "Delete the Nth Penultimate Node of linked list"

Popularity：485 ℃/2025-02-26 23:24:45

From fast and slow pointer to countdown search: Elegantly solve the problem of countdown of linked lists

Start with the life scene

Imagine you are in a long team and want to know how many people you have left before the end of the team. A clever way is to ask your friend to count N steps back from your position, and then you and your friend walk backwards. When your friend reaches the end of the team, your position is exactly Nth last. This little trick in life is the inspiration for the linked list algorithm we are going to explore today.

Problem description

LeetCode Question 19 "Delete the Nth-last node of the linked list" requirements: Give you a head node of the linked list head and an integer n, please delete the nth-last node of the linked list and return the head node of the linked list.

For example:

Input: 1 → 2 → 3 → 4 → 5, n = 2
 Output: 1 → 2 → 3 → 5
 Explanation: Delete the second last node (value is 4)

 Input: 1 → 2, n = 2
 Output: 2
 Explanation: Delete the second last node (value is 1)

 Input: 1, n = 1
 Output: empty link table
 Explanation: Delete the unique node

Preliminary idea: two traversal methods

The most intuitive solution is to traverse the linked list first to get the length, and then traverse the target node again and delete it:

public ListNode removeNthFromEnd(ListNode head, int n) {
     // The first traversal is calculating the length of the linked list
     int length = 0;
     ListNode current = head;
     while (current != null) {
         length++;
         current = ;
     }
    
     // If the header node is to be deleted
     if (length == n) {
         return ;
     }
    
     // Find the previous node to be deleted
     current = head;
     for (int i = 0; i < length - n - 1; i++) {
         current = ;
     }
    
     // Perform a delete operation
      = ;
    
     return head;
 }

Optimization solution: fast and slow pointer traversal

Just like our example in the team, we can solve the problem in one traversal with fast and slow pointers:

public ListNode removeNthFromEnd(ListNode head, int n) {
     // Create sentinel nodes to handle deletion of head nodes in a unified manner
     ListNode dummy = new ListNode(0);
      = head;
    
     // Initialize the fast and slow pointer
     ListNode fast = dummy;
     ListNode slow = dummy;
    
     // The fast pointer takes n+1 step first (one step is to make the slow pointer stop at the previous position of the node to be deleted)
     for (int i = 0; i <= n; i++) {
         fast = ;
     }
    
     // Fast and slow pointer moves synchronously
     while (fast != null) {
         fast = ;
         slow = ;
     }
    
     // Perform a delete operation
      = ;
    
     return ;
 }

Graphical process

Example: Delete the second last node
 1) Initial status:
 dummy → 1 → 2 → 3 → 4 → 5
 S,F

 2) Go to the fast pointer first n+1 step:
 dummy → 1 → 2 → 3 → 4 → 5
 S F

 3) Move synchronously until the fast pointer reaches the end:
 dummy → 1 → 2 → 3 → 4 → 5
             S F

 4) Delete nodes:
 dummy → 1 → 2 → 3 → 5

In-depth understanding of fast and slow pointer solutions

Why does this method work? Let's analyze it carefully:

  1. The fast pointer takes n+1 first, and generates a distance of n+1 from the slow pointer.
  2. When the fast pointer reaches the end (null), the slow pointer is exactly the previous position of the node to be deleted
  3. This ensures that we can always find the predecessor nodes to be deleted, making it easier to perform deletion operations

Complexity analysis

Two traversal methods:

  • Time complexity: O(L), two traversals are required
  • Space complexity: O(1)
  • Advantages: Intuitive and easy to understand
  • Disadvantages: Two traversals are required

Fast and Slow Pointer Method:

  • Time complexity: O(L), only one traversal
  • Space complexity: O(1)
  • Advantages: It can be completed in one traversal, more elegant
  • Disadvantages: You need to understand the principle of fast and slow pointers

Skill summary

  1. Use of sentinel nodes

    • Unified processing of head nodes
    • Avoid additional boundary checking

  2. Design of fast and slow pointer

    • A clever design of a fast pointer that takes n+1 steps first
    • Move synchronously until the fast pointer reaches the end

  3. Handling of boundary situations

    • The length of the linked list is equal to n
    • Only one node
    • n is equal to the length of the linked list

Extension of practical application

This fast and slow pointer idea has many applications in actual development:

  1. Cache Elimination Algorithm
  2. Sliding window processing for streaming data
  3. Delay calculation in real-time data processing

Summary and thoughts

Through this question, we learned:

  1. How to exchange space for time (two traversals)
  2. How to optimize space with clever algorithms (fast and slow pointer)
  3. The practical value of sentinel nodes
  4. How to handle the boundary situation of linked lists elegantly

When we encounter a similar "countdown" problem, we can consider:

  1. Can it be solved with fast and slow pointers?
  2. Is the Sentinel node simplified processing required?
  3. How to complete a task in one traversal?

Remember: Sometimes seemingly complex problems can be found with the right way of thinking.

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>