Coding interview problems › Linked Lists

🔗 Linked Lists Medium

Remove Nth Node From End of List

Remove the Nth node from the end of a linked list in one pass: open an n-node gap between two pointers, then move both. Tested Python, live visual.

Also searched as: delete nth node from end of linked list · two pointer gap technique linked list · nth node from the end in one pass

🔗

Try it live Free

Linked Lists: Reverse & Floyd's Cycle

Use the linked list lab to get comfortable re-pointing next links; this problem adds a second pointer that trails the first by a fixed gap.

Open the playground →

The problem

Given the head of a linked list and an integer n, remove the n-th node counting from the end and return the head of the updated list. You may assume 1 <= n <= the list length.

Input1 -> 2 -> 3 -> 4 -> 5, n = 2
Output1 -> 2 -> 3 -> 5

The 2nd node from the end is 4.

Input1, n = 1
Outputempty list

The key insight

Put two pointers n nodes apart and move them together. When the front one reaches the last node, the back one is sitting just before the node to delete. Starting both at a dummy node before the head means deleting the head itself needs no special case.

Brute force first: Count the length L in one pass, then walk to node L - n and unlink the next node. It is O(n) too, but takes two passes.

Step-by-step approach

  1. Create dummy with dummy.next = head; set fast = slow = dummy.
  2. Move fast forward n steps.
  3. Move both pointers one step at a time until fast.next is None.
  4. Now slow.next is the node to remove: set slow.next = slow.next.next.
  5. Return dummy.next, which may differ from the original head.

Python solution

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


def remove_nth_from_end(head, n):
    dummy = ListNode(0, head)
    fast = slow = dummy
    for _ in range(n):              # open a gap of n nodes
        fast = fast.next
    while fast.next:                # fast stops on the last node
        fast, slow = fast.next, slow.next
    slow.next = slow.next.next      # unlink the n-th node from the end
    return dummy.next

Complexity

TimeO(L)
SpaceO(1)

Where L is the list length, fast walks the list once and slow trails it, so it is one pass with two pointers of storage.

Common mistakes

Frequently asked questions

What is the time and space complexity?

O(L) time for one pass over a list of length L, and O(1) extra space.

Why use a dummy node?

When the node to remove is the head, there is no node before it. The dummy node provides one, so the same unlink line works in every case.

How do I just find the n-th node from the end without removing it?

Use the same gap: move fast n steps from the head, then move both until fast is None; slow is then the n-th node from the end.

Is the two-pass solution acceptable?

It is correct and also O(L). Interviewers often ask for one pass as a follow-up, which is what the gap technique gives.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Linked Lists Linked Lists: Reverse & Floyd's Cycle lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.