Remove Nth Node From End of List

Q: Why is the dummy node necessary?

When n equals the length, the head itself must go, and the head has no node before it to update. With a dummy in front, trail stops on the dummy, dummy.next is updated, and returning dummy.next gives the new head.

Q: Why does this matter for infra roles?

"The Nth item from the end" is the question behind tail -n, keeping only the last few releases for rollback, or pruning all but the newest backups. When the data is a one-way stream rather than a list you can hold two pointers into, tail solves it by keeping a ring buffer of the last n lines, which is the Design Circular Queue problem.

mediumLinked listAWS Cloud Support

You get the head of a singly linked list and an integer n. Remove the node that is n positions from the end of the list (so n = 1 is the last node) and return the head of the resulting list.

n is always between 1 and the length of the list, so the node to remove always exists. It may be the head itself.

Examples

Example 1

Input: head = 11 -> 22 -> 33 -> 44 -> 55, n = 2

Output: 11 -> 22 -> 33 -> 55

Explanation: Counting from the end, 55 is first and 44 is second, so 44 is removed.

Example 2

Input: head = 7, n = 1

Output: (empty list)

Explanation: The only node is also the last one, so removing it leaves nothing.

Hints

Approach

Use two pointers with a fixed gap so one pass is enough.

Start lead and trail at a dummy node placed before head.
Move lead forward n + 1 times. Now there are exactly n nodes between them.
Move both one step at a time until lead becomes null.
trail now sits just before the node that is n from the end. Unlink it and return dummy.next.

The extra + 1 step is what lands trail on the predecessor instead of the target, and the dummy node makes removing the head work without a special case.

ComplexityTime O(L), one passSpace O(1)

Python

# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
 
class Solution:
    def removeNthFromEnd(self, head: ListNode | None, n: int) -> ListNode | None:
        dummy = ListNode(0, head)        # handles removing the head itself
        lead = trail = dummy
        for _ in range(n + 1):           # open a gap of n nodes between them
            lead = lead.next
        while lead:                      # move both until lead falls off the end
            lead = lead.next
            trail = trail.next
        trail.next = trail.next.next     # trail is just before the target
        return dummy.next

Follow-up questions

What if n might be larger than the length? Return the list unchanged instead of crashing.
Return the value of the Nth node from the end of a stream you can only read once, using O(n) memory at most.

Frequently asked questions

When n equals the length, the head itself must go, and the head has no node before it to update. With a dummy in front, trail stops on the dummy, dummy.next is updated, and returning dummy.next gives the new head.

Not by much. Both are O(L), and the two pointers together still step through roughly the same number of nodes as two passes do. Interviewers ask for it because keeping a fixed-size gap between two pointers is a technique you will reuse, not because it is dramatically faster.

"The Nth item from the end" is the question behind tail -n, keeping only the last few releases for rollback, or pruning all but the newest backups. When the data is a one-way stream rather than a list you can hold two pointers into, tail solves it by keeping a ring buffer of the last n lines, which is the Design Circular Queue problem.

Problem statement