LeetCode Solutions Blog

Remove Nth Node From End of List

Number: 19

Difficulty: Medium

Paid? No

Problem Description

Given the head of a singly linked list, remove the nth node from the end of the list and return the modified list. This problem must be solved in one pass over the list.

Key Insights

Use a dummy node at the start to simplify edge cases, especially when the head is removed.
Utilize two pointers (fast and slow) and maintain a gap of n+1 nodes between them.
By moving both pointers simultaneously, the slow pointer will point to the node immediately before the target node when the fast pointer reaches the end.

Space and Time Complexity

Time Complexity: O(L), where L is the length of the list
Space Complexity: O(1)

Solution

We use a two-pointer approach to achieve a one-pass solution. A dummy node is created and linked to the head to handle edge cases gracefully (such as needing to remove the head). The fast pointer is advanced n+1 steps ahead of the slow pointer to maintain the required gap. Then, both pointers are moved simultaneously until the fast pointer reaches the end of the list. At that point, the slow pointer is immediately before the node to be deleted. We then adjust the pointers to remove the target node from the list.

Code Solutions

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val      # Holds the value of the node
        self.next = next    # Points to the next node in the list

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        # Create a dummy node to simplify edge cases (like removing the head)
        dummy = ListNode(0)
        dummy.next = head
        
        # Initialize two pointers starting at the dummy node
        first = dummy
        second = dummy
        
        # Advance first pointer n+1 steps ahead to maintain a gap of n nodes
        for _ in range(n + 1):
            first = first.next
        
        # Move both pointers until first reaches the end of the list
        while first:
            first = first.next
            second = second.next
        
        # Skip the node to remove it from the list
        second.next = second.next.next
        
        # Return the adjusted list starting from dummy.next
        return dummy.next