19. Remove Nth Node From End of List

Reformulated question¶

Remove the node that is n positions from the end of a singly linked list, and return the new head.

Example:

head=[1,2,3,4,5], n=2 -> remove 4 -> [1,2,3,5]

Key trick¶

Use two pointers with a dummy node:

Move fast ahead by n steps.
Then move fast and slow together until fast is at the end.
slow.next is the node to remove.

This gives one pass after setup and handles deleting the head cleanly.

Trap¶

Common mistakes:

Forgetting a dummy node, which makes removing the head awkward.
Off-by-one errors in the gap between fast and slow.
Not handling a one-element list.
In helpers, crashing on [] by returning nodes[0].

Why is this question interesting?¶

It tests linked-list pointer control:

local pointer updates
edge-case handling
converting a 2-pass idea into a 1-pass gap trick

Solution with idiomatic Python¶

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 simplifies deleting the head node.
        dummy = ListNode(0, head)
        fast = dummy
        slow = dummy

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

        # When fast reaches the end, slow is just before the node to remove.
        while fast.next:
            fast = fast.next
            slow = slow.next

        # Delete target node.
        slow.next = slow.next.next
        return dummy.next

Pytest test¶

import pytest

@pytest.mark.parametrize(
    ("values", "n", "expected"),
    [
        ([1, 2, 3, 4, 5], 2, [1, 2, 3, 5]),
        ([1], 1, []),
        ([1, 2], 1, [1]),
        ([1, 2], 2, [2]),
        ([1, 2, 3], 3, [2, 3]),
        ([1, 2, 3], 1, [1, 2]),
        ([1, 2, 3, 4], 4, [2, 3, 4]),
        ([1, 2, 3, 4], 2, [1, 2, 4]),
    ],
)
def test_remove_nth_from_end(values, n, expected):
    head = build_linked_list(values)
    got = Solution().removeNthFromEnd(head, n)
    assert linked_list_to_list(got) == expected

Comment my solution¶

Your solution works on the shown tests, but it is harder than needed.

Main remarks:

The standard two-pointer gap solution is shorter and easier to verify.
next = node.next is unused.
The node_cur_i - node_i <= n - 1 condition is not intuitive, so it is easy to introduce off-by-one bugs.
build_linked_list should handle [] safely if reused elsewhere.

from typing import Optional

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

    def __repr__(self):
        return f"ListNode({self.val})"

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        # We assume 1 <= n <= length of list head

        node_cur = head # parcour the list

        node = head # node to delete
        prev = None
        next = node.next

        node_cur_i = 0 # index in list of node_cur
        node_i = 0 # index in list of node

        while node_cur is not None:
            if node_cur_i - node_i <= n - 1:
                # move node_cur
                node_cur = node_cur.next
                node_cur_i += 1
            else:
                # move node
                prev = node
                node = node.next
                node_i += 1

        if node == head:
            return head.next
        else:
            prev.next = node.next if node.next is not None else None
            return head


## Test

import pytest

def build_linked_list(values):
    nodes = [ListNode(v) for v in values]
    for a, b in zip(nodes, nodes[1:]):
        a.next = b
    return nodes[0]


def linked_list_to_list(head):
    out = []
    cur = head
    while cur:
        out.append(cur.val)
        cur = cur.next
    return out

@pytest.mark.parametrize(
    ("values", "n", "expected"),
    [
        ([1, 2, 3, 4, 5], 2, [1, 2, 3, 5]),
        ([1], 1, []),
        ([1, 2], 1, [1]),
    ],
)
def test_delete_node(values, n, expected):
    head = build_linked_list(values)

    head_of_removed = Solution().removeNthFromEnd(head, n)

    assert linked_list_to_list(head_of_removed) == expected

A safer helper is:

def build_linked_list(values):
    dummy = ListNode()
    cur = dummy
    for v in values:
        cur.next = ListNode(v)
        cur = cur.next
    return dummy.next

Code¶

from typing import Optional
import pytest


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

    def __repr__(self):
        return f"ListNode({self.val})"


def build_linked_list(values):
    dummy = ListNode()
    cur = dummy
    for v in values:
        cur.next = ListNode(v)
        cur = cur.next
    return dummy.next


def linked_list_to_list(head):
    out = []
    cur = head
    while cur:
        out.append(cur.val)
        cur = cur.next
    return out


class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        # Dummy simplifies deleting the head node.
        dummy = ListNode(0, head)
        fast = dummy
        slow = dummy

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

        # When fast reaches the end, slow is just before the node to remove.
        while fast.next:
            fast = fast.next
            slow = slow.next

        # Delete target node.
        slow.next = slow.next.next
        return dummy.next


@pytest.mark.parametrize(
    ("values", "n", "expected"),
    [
        ([1, 2, 3, 4, 5], 2, [1, 2, 3, 5]),
        ([1], 1, []),
        ([1, 2], 1, [1]),
        ([1, 2], 2, [2]),
        ([1, 2, 3], 3, [2, 3]),
        ([1, 2, 3], 1, [1, 2]),
        ([1, 2, 3, 4], 4, [2, 3, 4]),
        ([1, 2, 3, 4], 2, [1, 2, 4]),
    ],
)
def test_remove_nth_from_end(values, n, expected):
    head = build_linked_list(values)
    got = Solution().removeNthFromEnd(head, n)
    assert linked_list_to_list(got) == expected