Skip to main content

🟨 Remove Nth Node From End of List (#19)

🔗 Problem Link​

📋 Problem Statement​

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

💡 Examples​

Example 1​

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

Example 2​

Input: head = [1], n = 1
Output: []

Example 3​

Input: head = [1,2], n = 1
Output: [1]

🔑 Key Insights & Approach​

Core Observation: Use two pointers separated by n nodes. When fast reaches end, slow points to node before target.

Why Two Pointers?

  • O(n) time, O(1) space
  • Single pass solution
  • No need to calculate length first

Approaches:

  1. Calculate length then remove: O(n) time, two passes
  2. Two pointers with gap: O(n) time, one pass - optimal

Pattern: "Fast and Slow Pointers" with fixed gap for nth from end problems.

🐍 Solution: Python​

Approach: Two Pointers with Gap​

Time Complexity: O(n) | Space Complexity: O(1)

from typing import Optional

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        # Dummy node to handle edge cases
        dummy = ListNode(0, head)
        fast = dummy
        slow = dummy

        # Move fast pointer n+1 steps ahead
        for _ in range(n + 1):
            fast = fast.next

        # Move both pointers until fast reaches end
        while fast:
            fast = fast.next
            slow = slow.next

        # Remove the nth node
        slow.next = slow.next.next

        return dummy.next

Approach 2: Without Dummy Node​

Time Complexity: O(n) | Space Complexity: O(1)

from typing import Optional

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        fast = slow = head

        # Move fast n steps ahead
        for _ in range(n):
            fast = fast.next

        # If fast is None, remove head
        if not fast:
            return head.next

        # Move both until fast reaches end
        while fast.next:
            fast = fast.next
            slow = slow.next

        # Remove node
        slow.next = slow.next.next

        return head

🔵 Solution: Golang​

Approach: Two Pointers​

Time Complexity: O(n) | Space Complexity: O(1)

type ListNode struct {
    Val  int
    Next *ListNode
}

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{Next: head}
    fast := dummy
    slow := dummy

    // Move fast n+1 steps ahead
    for i := 0; i <= n; i++ {
        fast = fast.Next
    }

    // Move both until fast reaches end
    for fast != nil {
        fast = fast.Next
        slow = slow.Next
    }

    // Remove node
    slow.Next = slow.Next.Next

    return dummy.Next
}

📚 References​