Medium

Remove Nth Node From End of List

LAB

Given a linked list encoded as an array, remove the nth node from the end and return the remaining values.

EXAMPLES

Example 1

Input
{
  "head": [
    1,
    2,
    3,
    4,
    5
  ],
  "n": 2
}

Output
[
  1,
  2,
  3,
  5
]

FUNCTION SHAPE

head: intArrayn: int→intArray

SOLUTION NOTE

The key insight is that by having the fast pointer n+1 steps ahead of the slow pointer, when the fast pointer reaches the end, the slow pointer will be at the node just before the one we want to remove. (instead of fast, slow, leading and lagging are better names because they travel at the same speed, they just start at different places) The dummy node helps handle the edge case of removing the first node. Try some examples.

Reveal reference solution +

pythonREFERENCE

def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
    # Iterative solution using the two-pointer technique
    # Dummy node to handle edge cases
    dummy = ListNode(0)
    dummy.next = head

    # Two pointers: fast and slow
    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 the end
    while fast:
        slow = slow.next
        fast = fast.next

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

    return dummy.next

# Recursive solution
def removeNthFromEndRecursive(self, head: ListNode, n: int) -> ListNode:
    # We'll use a helper function that returns the position from the end
    def remove_helper(node, n):
        # Base case: we've reached the end of the list
        if not node:
            return 0

        # Recursively process the rest of the list
        position = remove_helper(node.next, n) + 1

        # If this is the (n+1)th node from the end, remove the nth node
        if position == n + 1:
            node.next = node.next.next

        return position

    # Create a dummy node to handle edge cases
    dummy = ListNode(0)
    dummy.next = head

    # Start the recursive process
    remove_helper(dummy, n)

    return dummy.next

TimeO(n)

SpaceO(1) iterative, O(n) recursive

Open on LeetCode ↗