Remove Nth Node From End of List

Difficulty: Medium | Acceptance: 49.67% | Paid: No

Topics: Linked List, Two Pointers

• Examples
• Constraints
• Two-Pass Counting
• Two-Pointer Technique
• Recursive Approach

Examples

Input

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

Output

[1,2,3,5]

Input

head = [1], n = 1

Output

[]

Input

head = [1,2], n = 1

Output

[1]

Constraints

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

Two-Pass Counting

Intuition

We could count the total number of nodes in the first pass and then use that to find the nth node from the end and remove it.

Steps

• First, iterate through the entire list to count the total number of nodes.
• Calculate the position of the node to be removed from the start of the list using the formula: position = total_nodes - n + 1.
• Then, iterate again from the start to this position, keeping track of the previous node.
• When we reach the target node, adjust the pointers to remove it from the list.
• Handle edge cases like removing the head node by using a dummy node or special checks.

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

def removeNthFromEnd(head: ListNode, n: int) -> ListNode:
    dummy = ListNode(0)
    dummy.next = head
    current = head
    count = 0
    while current:
        count += 1
        current = current.next
    
    pos = count - n
    current = dummy
    for _ in range(pos):
        current = current.next
    
    current.next = current.next.next
    return dummy.next

Complexity

• Time: O(L), where L is the length of the list. We make two passes.
• Space: O(1) for the dummy node approach. No extra space is used.
• Notes: This approach is straightforward but requires two passes over the list.

Two-Pointer Technique

Intuition

We can use two pointers, where one is ahead of the other by n nodes. When the front pointer reaches the end, the rear pointer will be just before the node to remove.

Steps

• Initialize two pointers, ‘first’ and ‘second’, both pointing to a dummy node whose next points to head.
• Advance the ‘first’ pointer by n + 1 steps to create a gap of n nodes between the two pointers.
• Move both pointers at the same pace until ‘first’ reaches the end of the list.
• At this point, ‘second’ will be pointing to the node just before the one we need to remove.
• Adjust the pointers to remove the node from the list.
• Return the next node of the dummy node as the new head of the list.

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

def removeNthFromEnd(head: ListNode, n: int) -> ListNode:
    dummy = ListNode(0)
    dummy.next = head
    first = dummy
    second = dummy
    
    for _ in range(n + 1):
        first = first.next
    
    while first:
        first = first.next
        second = second.next
    
    second.next = second.next.next
    return dummy.next

Complexity

• Time: O(L), where L is the length of the list. We make one pass.
• Space: O(1) for the dummy node approach. No extra space is used.
• Notes: This approach is optimal as it only requires a single pass over the list and uses constant extra space.

Recursive Approach

Intuition

We can solve this problem by using a recursive traversal to the end of the list.

Steps

• Define a recursive helper function that traverses to the end of the list.
• As we return from the recursion, count the nodes from the end.
• When the count matches n, we know that the next node is the one to be removed.
• Adjust the pointers accordingly in the recursive call path.
• Handle the special case where the head node itself is to be removed by passing a reference to the head or using a dummy node.
• This is a clever but less common approach due to its space complexity.

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

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        def helper(node: ListNode) -> int:
            if not node:
                return 0
            count = helper(node.next)
            if count == n:
                node.next = node.next.next
            return count + 1
        
        dummy = ListNode(0)
        dummy.next = head
        helper(dummy)
        return dummy.next

Complexity

• Time: O(L), where L is the length of the list.
• Space: O(L) due to the recursion stack.
• Notes: While this approach works, it’s less efficient in terms of space and is not generally preferred in an interview setting where optimal space complexity is often desired.