19. Remove Nth Node From End of List (Medium)

Problem

Given the head of a linked list, remove the n-th node from the end and return the new head. Follow-up: do it in one pass.

Example

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

LeetCode 19 · Link · Medium

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, two passes (count, then remove)

First pass: count length L. Second pass: advance L - n steps, then splice.

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

def remove_nth_from_end(head, n):
    dummy = ListNode(0, head)
    L = 0
    cur = head
    while cur:                            # L1: first pass, count length
        L += 1                            # L2: O(1) per step
        cur = cur.next
    cur = dummy
    for _ in range(L - n):               # L3: second pass, advance L-n steps
        cur = cur.next                    # L4: O(1) per step
    cur.next = cur.next.next             # L5: O(1) splice
    return dummy.next

class ListNode {
    val: number; next: ListNode | null;
    constructor(val = 0, next: ListNode | null = null) { this.val = val; this.next = next; }
}

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
    const dummy = new ListNode(0, head);
    let L = 0;
    let cur: ListNode | null = head;
    while (cur) { L++; cur = cur.next; }   // L1-L2: first pass, count length
    let prev: ListNode = dummy;
    for (let i = 0; i < L - n; i++) {      // L3-L4: second pass, advance L-n steps
        prev = prev.next!;
    }
    prev.next = prev.next!.next;            // L5: O(1) splice
    return dummy.next;
}

type ListNode struct {
    Val  int
    Next *ListNode
}

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{Next: head}
    L := 0
    cur := head
    for cur != nil { L++; cur = cur.Next } // L1-L2: first pass, count length
    prev := dummy
    for i := 0; i < L-n; i++ {             // L3-L4: second pass, advance L-n steps
        prev = prev.Next
    }
    prev.Next = prev.Next.Next              // L5: O(1) splice
    return dummy.Next
}

final class Solution {
func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
        var count = 0
        var current = head
        while current != nil {
            count += 1
            current = current?.next
        }
        let dummy = ListNode(0, head)
        current = dummy
        for _ in 0..<(count - n) {
            current = current?.next
        }
        current?.next = current?.next?.next
        return dummy.next
    }
}

Where the time goes, line by line

Variables: L = number of nodes in the list, n = the parameter (position from end).

Line	Per-call cost	Times executed	Contribution
L1-L2 (count pass)	$O(1)$	L	$O(L)$
L3-L4 (advance pass)	$O(1)$	L - n	$O(L)$ ← dominates
L5 (splice)	$O(1)$	1	$O(1)$

Both passes are $O(L)$ ; together they give $O(2L)$ = $O(L)$ . The second pass only goes L - n steps, but in the worst case (n = 1) that’s still L - 1 steps.

Complexity

Time: $O(L)$ . Two passes, each $O(L)$ .
Space: $O(1)$ .

Works. Not one-pass.

Approach 2: Recursive removal counting from the end

Recurse to the end, then decrement a counter on the way back up; at n == 0, splice the previous node.

def remove_nth_from_end(head, n):
    dummy = ListNode(0, head)
    def rec(node):
        if not node:                         # L1: base case
            return 0
        k = rec(node.next) + 1              # L2: recurse deeper, O(1) on return
        if k == n + 1:
            node.next = node.next.next       # L3: O(1) splice at right depth
        return k
    rec(dummy)
    return dummy.next

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
    const dummy = new ListNode(0, head);
    function rec(node: ListNode | null): number {
        if (!node) return 0;                 // L1: base case
        const k = rec(node.next) + 1;       // L2: recurse deeper, O(1) on return
        if (k === n + 1) {
            node.next = node.next!.next;     // L3: O(1) splice at right depth
        }
        return k;
    }
    rec(dummy);
    return dummy.next;
}

type ListNode struct {
    Val  int
    Next *ListNode
}

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{Next: head}
    var rec func(node *ListNode) int
    rec = func(node *ListNode) int {
        if node == nil { return 0 }          // L1: base case
        k := rec(node.Next) + 1             // L2: recurse deeper, O(1) on return
        if k == n+1 {
            node.Next = node.Next.Next       // L3: O(1) splice at right depth
        }
        return k
    }
    rec(dummy)
    return dummy.Next
}

final class Solution {
func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
        let dummy = ListNode(0, head)
        var distanceFromEnd = 0
        func visit(_ node: ListNode?) {
            guard let node else { return }
            visit(node.next)
            distanceFromEnd += 1
            if distanceFromEnd == n + 1 {
                node.next = node.next?.next
            }
        }
        visit(dummy)
        return dummy.next
    }
}

Where the time goes, line by line

Variables: L = number of nodes in the list, n = the parameter (position from end).

Line	Per-call cost	Times executed	Contribution
L1 (base case)	$O(1)$	1	$O(1)$
L2 (recurse)	$O(1)$ per frame	L + 1	$O(L)$ ← dominates (stack depth)
L3 (splice)	$O(1)$	1	$O(1)$

The recursion unwinds L + 1 frames (including the dummy). Each frame does $O(1)$ work; all cost is in the stack depth.

Complexity

Time: $O(L)$ .
Space: $O(L)$ recursion depth.

Elegant but uses stack proportional to list length.

Approach 3: Two-pointer offset (optimal one-pass)

Advance fast by n + 1 steps, then walk both pointers together. When fast falls off, slow sits one before the node to remove.

def remove_nth_from_end(head, n):
    dummy = ListNode(0, head)
    slow = fast = dummy
    for _ in range(n + 1):              # L1: advance fast n+1 steps
        fast = fast.next                # L2: O(1) per step
    while fast:                         # L3: walk both until fast falls off
        slow = slow.next                # L4: O(1) per step
        fast = fast.next               # L5: O(1) per step
    slow.next = slow.next.next         # L6: O(1) splice
    return dummy.next

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
    const dummy = new ListNode(0, head);
    let slow: ListNode = dummy;
    let fast: ListNode | null = dummy;
    for (let i = 0; i <= n; i++) {      // L1-L2: advance fast n+1 steps
        fast = fast!.next;
    }
    while (fast) {                       // L3: walk both until fast falls off
        slow = slow.next!;              // L4: O(1) per step
        fast = fast.next;              // L5: O(1) per step
    }
    slow.next = slow.next!.next;        // L6: O(1) splice
    return dummy.next;
}

type ListNode struct {
    Val  int
    Next *ListNode
}

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{Next: head}
    slow, fast := dummy, dummy
    for i := 0; i <= n; i++ {           // L1-L2: advance fast n+1 steps
        fast = fast.Next
    }
    for fast != nil {                    // L3: walk both until fast falls off
        slow = slow.Next                 // L4: O(1) per step
        fast = fast.Next                 // L5: O(1) per step
    }
    slow.Next = slow.Next.Next           // L6: O(1) splice
    return dummy.Next
}

final class Solution {
func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
        let dummy = ListNode(0, head)
        var fast: ListNode? = dummy
        for _ in 0...n {
            fast = fast?.next
        }
        var slow: ListNode? = dummy
        while fast != nil {
            fast = fast?.next
            slow = slow?.next
        }
        slow?.next = slow?.next?.next
        return dummy.next
    }
}

Where the time goes, line by line

Variables: L = number of nodes in the list, n = the parameter (position from end).

Line	Per-call cost	Times executed	Contribution
L1-L2 (offset phase)	$O(1)$	n + 1	$O(n)$
L3-L5 (walk phase)	$O(1)$	L - n	$O(L)$ ← dominates
L6 (splice)	$O(1)$	1	$O(1)$

Total steps = (n + 1) + (L - n) = L + 1, so exactly one pass over the list. The dummy node ensures slow has a valid .next even when removing the head (n == L).

Complexity

Time: $O(L)$ . One pass.
Space: $O(1)$ .

Why the dummy node matters

When n == L (removing the head), the slow pointer needs to land “one before the head.” A dummy sentinel makes “one before the head” a real node, so the splice logic is uniform regardless of whether we’re removing the head.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

# Quick smoke tests, paste into a REPL or save as test_019.py and run.
# Uses the two-pointer offset approach (Approach 3).

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

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

def from_list(vals):
    dummy = ListNode()
    cur = dummy
    for v in vals:
        cur.next = ListNode(v)
        cur = cur.next
    return dummy.next

def remove_nth_from_end(head, n):
    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

def _run_tests():
    # Example: remove 2nd from end of [1,2,3,4,5] -> [1,2,3,5]
    assert to_list(remove_nth_from_end(from_list([1,2,3,4,5]), 2)) == [1,2,3,5]
    # Single element, remove it
    assert to_list(remove_nth_from_end(from_list([1]), 1)) == []
    # Two elements, remove last
    assert to_list(remove_nth_from_end(from_list([1,2]), 1)) == [1]
    # Two elements, remove first (n == L)
    assert to_list(remove_nth_from_end(from_list([1,2]), 2)) == [2]
    # Remove head of longer list
    assert to_list(remove_nth_from_end(from_list([1,2,3,4,5]), 5)) == [2,3,4,5]
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

class ListNode {
    val: number; next: ListNode | null;
    constructor(val = 0, next: ListNode | null = null) { this.val = val; this.next = next; }
}

function toList(head: ListNode | null): number[] {
    const out: number[] = [];
    while (head) { out.push(head.val); head = head.next; }
    return out;
}

function fromList(vals: number[]): ListNode | null {
    const dummy = new ListNode();
    let cur = dummy;
    for (const v of vals) { cur.next = new ListNode(v); cur = cur.next; }
    return dummy.next;
}

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
    const dummy = new ListNode(0, head);
    let slow: ListNode = dummy, fast: ListNode | null = dummy;
    for (let i = 0; i <= n; i++) fast = fast!.next;
    while (fast) { slow = slow.next!; fast = fast.next; }
    slow.next = slow.next!.next;
    return dummy.next;
}

console.assert(JSON.stringify(toList(removeNthFromEnd(fromList([1,2,3,4,5]), 2))) === JSON.stringify([1,2,3,5]));
console.assert(JSON.stringify(toList(removeNthFromEnd(fromList([1]), 1))) === JSON.stringify([]));
console.assert(JSON.stringify(toList(removeNthFromEnd(fromList([1,2]), 1))) === JSON.stringify([1]));
console.assert(JSON.stringify(toList(removeNthFromEnd(fromList([1,2]), 2))) === JSON.stringify([2]));
console.assert(JSON.stringify(toList(removeNthFromEnd(fromList([1,2,3,4,5]), 5))) === JSON.stringify([2,3,4,5]));
console.log("all tests pass");

Summary

Approach	Time	Space	Passes
Two-pass count + remove	$O(L)$	$O(1)$	2
Recursive	$O(L)$	$O(L)$ stack	1
Two-pointer offset	$O(L)$	$O(1)$	1

The offset-n two-pointer trick generalizes to “find the k-th from end” and variants.

Linked Lists, two-pointer distance pattern with dummy head

Fast and Slow Pointers, the pointer speed trick for finding middles, cycles, and distance from the end.
Linked List Pointer Rewiring, the link editing pattern for changing node order without losing the chain.

19. Remove Nth Node From End of List (Medium)

Problem

Try it yourself

Approach 1: Brute force, two passes (count, then remove)

Approach 2: Recursive removal counting from the end

Approach 3: Two-pointer offset (optimal one-pass)

Why the dummy node matters

Test cases

Summary

Related data structures

Related concepts