MediumLinked ListTwo Pointers

Remove Nth Node From End of List

1 approach, code in every language

Given the head of a singly linked list and an integer n, delete the node that sits n positions from the end of the list and return the head of the modified list.

The counting is from the tail: n equal to 1 means the last node, n equal to 2 means the second-to-last, and so on. Aim to do this in a single pass over the list.

Example 1

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

Output: [1,2,3,5]

The second node from the end holds value 4, so it is removed.

Example 2

Input: head = [1], n = 1

Output: []

Removing the only node from a one-element list yields an empty list.

Constraints

The number of nodes is in the range [1, 30].
1 <= Node.val <= 100
1 <= n <= number of nodes

Two Pointers with a Fixed Gap

Keep a lead pointer n+1 steps ahead so the trailing pointer stops just before the target.

Loading animation…

Intuition

Removing a node requires standing on the node right before it so we can rewire the next pointer. To find that predecessor in one pass, open a gap of n + 1 nodes between a fast and a slow pointer. When the fast pointer walks off the end, the slow pointer is precisely one node ahead of the one we need to delete. A dummy node placed before the head removes the special case of deleting the very first node, since the dummy always has a valid predecessor. We then unlink the target and return the node after the dummy.

Algorithm walkthrough

1Create a dummy node whose next points to head, and set both slow and fast to the dummy.
2Advance fast by n + 1 steps so the gap between fast and slow is exactly n + 1.
3Move slow and fast together, one node at a time, until fast becomes null.
4Now slow sits just before the node to delete; set slow.next to slow.next.next to skip it.
5Return dummy.next as the new head of the list.

Implementation

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        slow = fast = dummy
        for _ in range(n + 1):
            fast = fast.next
        while fast:
            slow = slow.next
            fast = fast.next
        slow.next = slow.next.next
        return dummy.next

Time

O(n)

Space

O(1)

A single traversal removes the node; the dummy avoids edge-case branching.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Linked List

After the pattern

Now solve one you haven't seen.

Unhook the Nth Wagon from the Tail is our own problem on the technique behind Remove Nth Node From End of List: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free