LeetCode 19: Remove Nth Node From End of List

Problem Statement

Given a linked list and an integer n, remove the nth node from the end of the list and return the head of the modified list. The list has at least one node, and n is guaranteed to be valid (1 ≤ n ≤ list length).

Constraints

Number of nodes in the list is between 1 and 30.
0 <= Node.val <= 100
1 <= n <= list length

Example

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
Explanation: Remove 4 (2nd from end).

Input: head = [1], n = 1
Output: []
Explanation: Remove 1 (only node).

Input: head = [1,2], n = 1
Output: [1]
Explanation: Remove 2 (last node).

Understanding the Problem

We need to delete the nth node from the end of a linked list, like removing 4 from [1,2,3,4,5] when n = 2, leaving [1,2,3,5]. Since it’s a singly linked list, we can’t traverse backward, so we’ll use a two-pointer technique to find and remove the target node efficiently in one pass.

Solution: Two-Pointer Technique

Explanation

Use two pointers—fast and slow—where fast moves n nodes ahead, then both move until fast reaches the end, leaving slow at the node before the target. Adjust links to skip the target node.

Create Dummy Node.

Add a dummy node before head to handle edge cases (e.g., removing the first node).

Set Fast Pointer.

Move fast pointer n nodes ahead.

Move Both Pointers.

Move fast and slow together until fast reaches the end; slow will be before the target.

Remove Target Node.

Link slow’s next to skip the nth node from the end.

Return Head.

Return dummy.next as the new head.

Step-by-Step Example

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

We have [1,2,3,4,5] and want to remove the 2nd node from the end.

Goal: Remove 4, leaving [1,2,3,5].
Result for Reference: [1,2,3,5].
Start: Add dummy node, list becomes dummy -> 1 -> 2 -> 3 -> 4 -> 5.
Step 1: Set fast pointer.

Fast starts at dummy.
Move n = 2: dummy -> 1 -> 2.
Fast is at 2.

Step 2: Set slow pointer.

Slow starts at dummy.

Step 3: Move both pointers.

Fast at 2, slow at dummy, move both.
Fast to 3, slow to 1.
Fast to 4, slow to 2.
Fast to 5, slow to 3.
Fast to null (end), slow at 3.

Step 4: Remove target node.

Slow at 3, next is 4 (target), next.next is 5.
Link 3.next to 5, skipping 4.
List: dummy -> 1 -> 2 -> 3 -> 5.

Step 5: Return head.

Return dummy.next = [1,2,3,5].

Finish: Result is [1,2,3,5].

Example 2: head = [1], n = 1

Now, [1] with n = 1.

Goal: Remove 1, leaving [].
Result for Reference: [].
Start: Dummy -> 1.
Step 1: Fast moves 1: dummy -> 1.
Step 2: Slow at dummy.
Step 3: Move both.

Fast to null, slow to dummy.

Step 4: Slow.next is 1, link to null.

Dummy -> null.

Step 5: Return dummy.next = null (empty list).
Finish: Result is [].

Code (Two-Pointer Technique)

Here’s the efficient Python code for LeetCode 19. It works in Python 3.6+. Test it on Replit!

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

def removeNthFromEnd(head: ListNode, n: int) -> ListNode:
    # Add dummy node to handle edge cases
    dummy = ListNode(0)
    dummy.next = head
    fast = slow = dummy

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

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

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

    return dummy.next

Complexity

Time Complexity: O(n) – Single pass through the list, where n is the list length.
Space Complexity: O(1) – Only uses two pointers and a dummy node.

Efficiency Notes

This two-pointer method is optimal, achieving O(n) time with one pass, avoiding the need for multiple traversals or extra space.

Key Insights

Tips to master LeetCode 19:

Dummy Node Saves Hassle: It simplifies edge cases like removing the head—always use it!
Two Pointers Shine: Fast-ahead-then-sync is perfect for end-based problems.
Link Carefully: Ensure pointers align to skip the target node cleanly.

Alternative: Length-Based Approach

Explanation

Calculate list length first, then traverse to the node before the target to remove it. Requires two passes but is straightforward.

Get Length.

Traverse to count nodes.

Find Target Position.

Calculate position from start (length - n).

Remove Node.

Traverse to node before target, adjust links.

Return Head.

Return modified list head.

Step-by-Step Example (Length-Based)

For [1,2,3,4,5], n = 2:

Goal: Remove 4.
Reference: [1,2,3,5].
Start: Dummy -> 1 -> 2 -> 3 -> 4 -> 5.
Step 1: Length = 5.
Step 2: Target position = 5 - 2 = 3 (node 4, 0-based index 3).

Node before is index 2 (value 3).

Step 3: Traverse to index 2.

Dummy -> 1 -> 2 -> 3.
3.next = 4, link to 5.
Dummy -> 1 -> 2 -> 3 -> 5.

Step 4: Return dummy.next.
Finish: [1,2,3,5].

Code (Length-Based Approach)

Here’s the alternative Python code, less efficient but clear.

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

def removeNthFromEndLength(head: ListNode, n: int) -> ListNode:
    dummy = ListNode(0)
    dummy.next = head

    # Get length
    length = 0
    curr = head
    while curr:
        length += 1
        curr = curr.next

    # Find node before target
    target_prev = length - n
    curr = dummy
    for _ in range(target_prev):
        curr = curr.next

    # Remove target node
    curr.next = curr.next.next

    return dummy.next

Complexity (Both Solutions)

Two-Pointer:

Time: O(n) – One pass.
Space: O(1) – Constant extra space.

Length-Based:

Time: O(n) – Two passes (length + removal).
Space: O(1) – Constant extra space.

Efficiency Notes

Two-pointer is preferred for its single-pass efficiency, while length-based is simpler but requires two traversals.

Key Insights

Tips to master LeetCode 19:

Use dummy nodes to handle head removal cleanly
Two pointers beat multiple passes for speed
Test edge cases like single nodes early

Additional Example

For head = [1,2,3], n = 3:

Goal: Remove 1.
Reference: [2,3].
Two-Pointer: Fast to 3, slow at dummy, link to 2.
Result: [2,3].

Edge Cases

Single Node: [1], n = 1 – Returns [].
Remove Head: [1,2], n = 2 – Returns [2].
Remove Last: [1,2], n = 1 – Returns [1].

Final Thoughts

The two-pointer technique is a slick way to solve LeetCode 19 in Python, efficient and elegant. Check LeetCode 21: Merge Two Sorted Lists for more linked list practice!