deepSWE.io

Remove Nth Node From End of List

Two PointersLinked List

MediumLeetCode #19

15-20 min

Problem Statement

Given the head of a linked list, remove the n-th node from the end of the list and return its head.

Example

Example 1:

Input: head = [1,2,3,4,5], n = 2

Output: [1,2,3,5]

The 2nd node from the end (value 4) is removed.

Constraints

• The number of nodes in the list is sz.
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

Solutions

Approach 1: Two-Pass Algorithm

A straightforward but less efficient approach is to traverse the linked list twice. The first pass is to determine the total number of nodes (the length of the list), and the second pass is to locate and remove the nth node from the end.

Algorithm Steps

First Pass: Traverse the entire list to count the total number of nodes, let's call it length.
Calculate the position of the node to remove from the beginning: target_index = length - n.
Handle the edge case where the head node needs to be removed (i.e., target_index === 0).
Second Pass: Traverse the list again up to the node just before the target node (at target_index - 1).
Update the next pointer of this preceding node to skip the target node, effectively removing it.

While this method is easy to understand, its main drawback is the need for two full traversals of the list, making it less optimal than a single-pass solution.

Two-Pass Solution


class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        length = 0
        temp = head
        while temp:
            length += 1
            temp = temp.next
        
        if length == n:
            return head.next
            
        target_index = length - n
        temp = head
        for _ in range(target_index - 1):
            temp = temp.next
        
        temp.next = temp.next.next
        return head

Approach: Two Pointers

The optimal solution uses a two-pointer technique to find the nth node from the end in a single pass. This avoids the need to first traverse the list to find its length.

Step 0 | Slow: Node 1 | Fast: Node 1

Algorithm Steps

Initialize two pointers, slow and fast, at the head of the list.
Move the fast pointer n steps ahead.
If fast becomes null, the head is the node to be removed.
Move both slow and fast one step at a time until fast reaches the last node.
The slow pointer will now be at the node just before the one to be removed.
Update slow.next to skip the target node.

Two-Pointers Solution


class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        # Initialize two pointers, fast and slow, at the head.
        fast = head
        slow = head

        # Move the fast pointer n steps forward.
        for _ in range(n):
            fast = fast.next

        # If fast is None, it means n is the length of the list,
        # so we need to remove the head.
        if not fast:
            return head.next

        # Move both pointers until fast reaches the last node.
        # Slow will then be at the node right before the one to remove.
        while fast.next:
            fast = fast.next
            slow = slow.next

        # Bypass the node to be removed.
        slow.next = slow.next.next
        
        return head