Remove Nth Node From End of List

Remove the nth node from the end of a linked list in one pass

Language Selection

Choose your preferred programming language

Showing: Python

Problem Statement

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

Input/Output Specifications

Input: Head of a linked list and integer n
Output: Head of the modified linked list
Constraints:
- The number of nodes in the list is sz
- 1 <= sz <= 30
- 0 <= Node.val <= 100
- 1 <= n <= sz

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]

Solutions

Approach 1: Two Pass (Count First)

This approach first counts the total number of nodes, then calculates the position from the beginning and removes the node.

Algorithm:

First pass: count the total number of nodes
Calculate the position from the beginning: length - n + 1
Second pass: traverse to the node before the target and remove it
Handle edge case where we need to remove the head

Python:

def removeNthFromEnd(head, n):
    """
    Remove nth node from end using two passes
    Time: O(n)
    Space: O(1)
    """
    # First pass: count nodes
    length = 0
    current = head
    while current:
        length += 1
        current = current.next
    
    # Calculate position from beginning
    pos = length - n
    
    # If removing head
    if pos == 0:
        return head.next
    
    # Second pass: find node before target
    current = head
    for i in range(pos - 1):
        current = current.next
    
    # Remove the target node
    current.next = current.next.next
    
    return head

Java:

class Solution {
    /**
     * Remove nth node from end using two passes
     * Time: O(n)
     * Space: O(1)
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // First pass: count nodes
        int length = 0;
        ListNode current = head;
        while (current != null) {
            length++;
            current = current.next;
        }
        
        // Calculate position from beginning
        int pos = length - n;
        
        // If removing head
        if (pos == 0) {
            return head.next;
        }
        
        // Second pass: find node before target
        current = head;
        for (int i = 0; i < pos - 1; i++) {
            current = current.next;
        }
        
        // Remove the target node
        current.next = current.next.next;
        
        return head;
    }
}

Go:

// removeNthFromEnd - Remove nth node from end using two passes
// Time: O(n)
// Space: O(1)
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    // First pass: count nodes
    length := 0
    current := head
    for current != nil {
        length++
        current = current.Next
    }
    
    // Calculate position from beginning
    pos := length - n
    
    // If removing head
    if pos == 0 {
        return head.Next
    }
    
    // Second pass: find node before target
    current = head
    for i := 0; i < pos-1; i++ {
        current = current.Next
    }
    
    // Remove the target node
    current.Next = current.Next.Next
    
    return head
}

JavaScript:

/**
 * Remove nth node from end using two passes
 * Time: O(n)
 * Space: O(1)
 */
function removeNthFromEnd(head, n) {
    // First pass: count nodes
    let length = 0;
    let current = head;
    while (current !== null) {
        length++;
        current = current.next;
    }
    
    // Calculate position from beginning
    const pos = length - n;
    
    // If removing head
    if (pos === 0) {
        return head.next;
    }
    
    // Second pass: find node before target
    current = head;
    for (let i = 0; i < pos - 1; i++) {
        current = current.next;
    }
    
    // Remove the target node
    current.next = current.next.next;
    
    return head;
}

C#:

public class Solution {
    /// <summary>
    /// Remove nth node from end using two passes
    /// Time: O(n)
    /// Space: O(1)
    /// </summary>
    public ListNode RemoveNthFromEnd(ListNode head, int n) {
        // First pass: count nodes
        int length = 0;
        ListNode current = head;
        while (current != null) {
            length++;
            current = current.next;
        }
        
        // Calculate position from beginning
        int pos = length - n;
        
        // If removing head
        if (pos == 0) {
            return head.next;
        }
        
        // Second pass: find node before target
        current = head;
        for (int i = 0; i < pos - 1; i++) {
            current = current.next;
        }
        
        // Remove the target node
        current.next = current.next.next;
        
        return head;
    }
}

Approach 2: One Pass (Two Pointers)

This approach uses two pointers with a gap of n nodes between them. When the fast pointer reaches the end, the slow pointer will be at the node before the target.

Algorithm:

Create a dummy head to handle edge cases
Move the fast pointer n steps ahead
Move both pointers until fast reaches the end
Remove the target node by updating the slow pointer’s next
Return the head (skip dummy)

Python:

def removeNthFromEndOnePass(head, n):
    """
    Remove nth node from end using one pass with two pointers
    Time: O(n)
    Space: O(1)
    """
    dummy = ListNode(0)
    dummy.next = head
    
    slow = fast = dummy
    
    # Move fast pointer n steps ahead
    for _ in range(n + 1):
        fast = fast.next
    
    # Move both pointers until fast reaches end
    while fast:
        slow = slow.next
        fast = fast.next
    
    # Remove the target node
    slow.next = slow.next.next
    
    return dummy.next

Java:

class Solution {
    /**
     * Remove nth node from end using one pass with two pointers
     * Time: O(n)
     * Space: O(1)
     */
    public ListNode removeNthFromEndOnePass(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        ListNode slow = dummy;
        ListNode fast = dummy;
        
        // Move fast pointer n steps ahead
        for (int i = 0; i <= n; i++) {
            fast = fast.next;
        }
        
        // Move both pointers until fast reaches end
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        
        // Remove the target node
        slow.next = slow.next.next;
        
        return dummy.next;
    }
}

Go:

// removeNthFromEndOnePass - Remove nth node from end using one pass with two pointers
// Time: O(n)
// Space: O(1)
func removeNthFromEndOnePass(head *ListNode, n int) *ListNode {
    dummy := &ListNode{Val: 0, Next: head}
    
    slow := dummy
    fast := dummy
    
    // Move fast pointer n steps ahead
    for i := 0; i <= n; i++ {
        fast = fast.Next
    }
    
    // Move both pointers until fast reaches end
    for fast != nil {
        slow = slow.Next
        fast = fast.Next
    }
    
    // Remove the target node
    slow.Next = slow.Next.Next
    
    return dummy.Next
}

JavaScript:

/**
 * Remove nth node from end using one pass with two pointers
 * Time: O(n)
 * Space: O(1)
 */
function removeNthFromEndOnePass(head, n) {
    const dummy = new ListNode(0);
    dummy.next = head;
    
    let slow = dummy;
    let fast = dummy;
    
    // Move fast pointer n steps ahead
    for (let i = 0; i <= n; i++) {
        fast = fast.next;
    }
    
    // Move both pointers until fast reaches end
    while (fast !== null) {
        slow = slow.next;
        fast = fast.next;
    }
    
    // Remove the target node
    slow.next = slow.next.next;
    
    return dummy.next;
}

C#:

public class Solution {
    /// <summary>
    /// Remove nth node from end using one pass with two pointers
    /// Time: O(n)
    /// Space: O(1)
    /// </summary>
    public ListNode RemoveNthFromEndOnePass(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        ListNode slow = dummy;
        ListNode fast = dummy;
        
        // Move fast pointer n steps ahead
        for (int i = 0; i <= n; i++) {
            fast = fast.next;
        }
        
        // Move both pointers until fast reaches end
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        
        // Remove the target node
        slow.next = slow.next.next;
        
        return dummy.next;
    }
}

Key Insights

Two-pointer technique: Use fast and slow pointers with a gap to find the target in one pass
Dummy node: Simplifies edge cases, especially when removing the head
Gap maintenance: Keep n+1 gap between pointers to land on the node before target
One pass optimization: More efficient than counting nodes first
Edge case handling: Dummy node eliminates special cases for head removal

Edge Cases

Removing the head node (n equals list length)
Single node list
Two node list
n equals 1 (removing last node)
n equals list length (removing first node)

Test Cases

# Test case 1: Remove middle node
head1 = ListNode(1)
head1.next = ListNode(2)
head1.next.next = ListNode(3)
head1.next.next.next = ListNode(4)
head1.next.next.next.next = ListNode(5)
# removeNthFromEnd(head1, 2) -> [1,2,3,5]

# Test case 2: Remove head
head2 = ListNode(1)
head2.next = ListNode(2)
# removeNthFromEnd(head2, 2) -> [2]

# Test case 3: Remove last node
head3 = ListNode(1)
head3.next = ListNode(2)
# removeNthFromEnd(head3, 1) -> [1]

# Test case 4: Single node
head4 = ListNode(1)
# removeNthFromEnd(head4, 1) -> []

Follow-up Questions

How would you remove the nth node from the beginning?
Can you solve this without using a dummy node?
How would you handle invalid n values?
What if you need to remove multiple nodes?

Common Mistakes

Not handling the case where head needs to be removed
Incorrect gap calculation between pointers
Off-by-one errors in pointer movement
Not using dummy node to simplify edge cases
Forgetting to update the next pointer correctly
Index out of bounds when n is invalid