Skip to content

Volume ITechnology

4.9.4 — Remove Nth Node From End of List ​

LeetCode 19 · Medium · ★ Blind 75

The problem ​

You are given the head of a linked list and a number n. Remove the n-th node counting from the end, and return the head of the changed list.

1 → 2 → 3 → 4 → 5,  n = 2   →   1 → 2 → 3 → 5      (4 is 2nd from the end)
1,                  n = 1   →   (empty list)
1 → 2,              n = 1   →   1

The list has between 1 and 30 nodes, and n is always between 1 and the list's length. A follow-up asks you to do it in one pass through the list.

What the problem is really asking ​

To remove a node from a singly linked list, you need the node just before it. Then you make that node skip over the target: before.next = before.next.next.

So the real question is: how do you stop on the node just before the n-th-from-last, when you can only walk forwards and you do not know how long the list is?

The brute force: two passes ​

  1. Walk the whole list and count its length, L.
  2. The target is at position L - n counting from 0. Walk again and stop on the node before it.
  3. Skip over the target.
python
def removeNthFromEnd(head, n):
    length = 0
    node = head
    while node:
        length += 1
        node = node.next
    dummy = ListNode(0, head)
    before = dummy
    for _ in range(length - n):        # stop just before the target
        before = before.next
    before.next = before.next.next
    return dummy.next

This is already O(n) time and O(1) memory. It is a fine answer.

Its one weakness: it walks the list twice. If the list were data arriving over a network that you could only read once, you could not go back to the start for the second pass. That is why the follow-up asks for one pass.

The idea: a fixed gap ​

Use two pointers with a fixed distance between them.

  1. Move fast ahead by n nodes. Now there is a gap of n between slow and fast.
  2. Move both forward together, one step at a time. The gap never changes.
  3. When fast reaches the last node, slow is exactly n nodes behind it. That puts slow on the node just before the target.

Think of a measuring tape exactly n nodes long. You slide the whole tape along the list. When its front end touches the last node, its back end is exactly where you need it.

n = 2, both pointers start at a dummy node in front of the list

dummy → 1 → 2 → 3 → 4 → 5
  ↑         ↑
 slow      fast          after opening a gap of 2

dummy → 1 → 2 → 3 → 4 → 5
                ↑       ↑
               slow    fast    fast is on the last node, so stop

slow is on node 3, and the node after it, node 4, is the target.

The solution ​

python
class Solution:
    def removeNthFromEnd(self, head, n: int):
        dummy = ListNode(0, head)          # (1)
        slow = fast = dummy                # (2)

        for _ in range(n):                 # (3)
            fast = fast.next

        while fast.next:                   # (4)
            slow = slow.next
            fast = fast.next

        slow.next = slow.next.next         # (5)

        return dummy.next                  # (6)
ts
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  const dummy = new ListNode(0, head);     // (1)
  let slow = dummy, fast = dummy;          // (2)

  for (let i = 0; i < n; i++) {            // (3)
    fast = fast.next!;
  }

  while (fast.next) {                      // (4)
    slow = slow.next!;
    fast = fast.next;
  }

  slow.next = slow.next!.next;             // (5)

  return dummy.next;                       // (6)
}

Line by line ​

(1) A dummy node in front of the head. ListNode(0, head) makes a node with value 0 whose next is the real head. Here the dummy does real work, not just tidying. If the target is the head itself, as in 1 with n = 1, there is no node before it to re-link. The dummy gives the head a node before it, just like every other node.

(2) Both pointers start at the dummy, not at the head. That is what makes slow stop one node before the target. If they started at the head, slow would stop on the target, and you cannot remove a node from a singly linked list while standing on it.

(3) Open the gap. Move fast forward n times.

(4) Slide both together until fast is on the last node. The check is fast.next, not fast. We want fast to stop on the last node, not to step past it into None. One extra step would leave slow one node too far along.

(5) Skip over the target. slow.next is the target. Pointing slow.next at the node after the target removes it from the chain.

(6) Return the real head. If the original head was removed, dummy.next is now the second node, or None. Either way, dummy.next is correct. Returning head would be wrong in that case, because head still points at the removed node.

Trace ​

Take 1 → 2 → 3 → 4 → 5 and n = 2. After line (3), slow is on the dummy and fast is on node 2.

Stepslowfastfast.next empty?
startdummy2no
113no
224no
335yes, stop

slow is on node 3, and slow.next is node 4. Line (5) makes node 3 point to node 5. The result is 1 → 2 → 3 → 5. ✓

Now the hard case: 1 with n = 1. Line (3) moves fast from the dummy to node 1. In line (4), fast.next is already None, so the loop never runs, and slow stays on the dummy. Line (5) makes dummy.next equal to node 1's next, which is None. Line (6) returns None, the empty list. ✓

Complexity, derived ​

Time. fast moves from the dummy to the last node, which is L steps for a list of L nodes. slow moves L - n steps alongside it. Every step is constant work, and nothing is walked twice. So the time is O(L), in one pass.

Space. One dummy node and two pointers. So the extra memory is O(1).

The two-pass version has the same time and memory. One pass is not faster in theory. It matters only when the data can be read just once.

Edge cases ​

  • Removing the head, as in 1 → 2 with n = 2. slow stays on the dummy, and line (5) makes the dummy skip node 1. Handled by the dummy.
  • A single node with n = 1. Shown in the trace. Returns an empty list.
  • Removing the last node, n = 1. slow ends on the second-to-last node, which then points to None.

Run each of these in your head before you say you are done. They are where this problem's bugs live.

Variations you will meet ​

The fixed-gap pair of pointers turns up whenever a question is phrased "from the end".

  • Middle of the Linked List. Instead of a fixed gap, one pointer moves twice as fast, so the gap is always half the distance travelled.
  • Linked List Cycle. The same two pointers at different speeds, used to detect a loop. See 4.9.7.
  • The last k lines of a log file, read as it arrives. Keep a gap of k between what you have read and what you are keeping.

The general lesson: to reach a position counted from the end in one pass, open a gap and move both pointers together.

What the interviewer will push on ​

"Why the dummy node?" So that removing the head needs no special case.

"Why do both pointers start at the dummy?" So slow stops one node before the target, because removal needs the node before.

"Why while fast.next and not while fast?" So fast stops on the last node. One step further would put slow on the target instead of before it.

"What if n were bigger than the list?" The problem promises it is not. In real code you would check, because line (3) would try to step past None.

One thing to volunteer: say what happens when the target is the head, before they ask. It is the case this problem is built around.

Next: 4.9.5 Copy List with Random Pointer. A full copy of a list where an extra pointer can point anywhere.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet