Remove Nth Node From End of List

Q: How do you remove the nth node from the end of a linked list in one pass?

Use two pointers with a gap of n . Move the first one n nodes ahead, then move both together until the first one is on the last node. The second one now stands right before the node to remove, so you point its link past that node. If the first pointer runs off the list during its head start, the node to remove is the head.

Q: What is the time and space complexity of removing the nth node from the end?

It takes O(L) time for a list of L nodes, since you have to reach the end to know where the target is. Counting first and the two pointer method both use O(1) extra memory. Copying the values into an array uses O(L) .

Q: Is the two pointer solution faster than counting the length first?

Not by much: both are O(L) , and the two pointers together still make about as many moves as two walks would. The real gain is that you never need the length up front, so the method also works when the list arrives as a stream you can read only once. That single pass is what interviewers usually ask for.

MediumLinked list Two pointers

+10

You get a singly linked list stored in two arrays of the same length. Node i holds the value values[i] and links to node next[i], -1 ends the list, and the head is node 0. The nodes are not stored in list order, so follow the links.

Remove the n-th node counting from the end of the list, where the last node is the 1st from the end. Return the values of the nodes that remain, in list order.

Function

removeNthFromEnd(values: integer-array, next: integer-array, n: integer) → integer-array

valuesinteger-array: the value held by each node
nextinteger-array: the index of the node each node links to, or -1 for the last node
ninteger: which node to remove, counting from the end, where 1 is the last node
Returnsinteger-array: the remaining values in list order, empty when the only node is removed

Constraints

1 ≤ L ≤ 5000, where L is the length of values and of next.
-100 ≤ values[i] ≤ 100
1 ≤ n ≤ L
Each next[i] is -1 or a node index from 0 to L-1.
Starting at node 0, the list visits every node exactly once and then reaches -1. There is no cycle.

Examples

Input: values = [5, 9, 2, 7, 6]next = [2, 3, 4, -1, 1]n = 2
Output: [5, 2, 6, 7]
Explanation: Following the links from node 0 visits nodes 0, 2, 4, 1, 3, so the list reads 5, 2, 6, 9, 7. The 2nd from the end is node 1, value 9, and without it the list reads 5, 2, 6, 7. The array entry values[5-2] = 7 is the last node, not the one to remove.

Input: values = [10, 20, 30, 40]next = [1, 2, 3, -1]n = 4
Output: [20, 30, 40]
Explanation: Four nodes and n = 4: the node 4th from the end is the head. The list now starts at node 1 and reads 20, 30, 40.

Input: values = [42]next = [-1]n = 1
Output: []
Explanation: The only node is both the head and the last node. Removing it leaves an empty list, so the answer is [].

+14 hidden tests on Submit

Follow-up

Can you find and unlink the node in a single pass, without counting the length first?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

The target is defined by its distance from the end, but a singly linked list only lets you walk forward, and you learn where the end is only when you reach it. Removing a node also means standing on the node before it, because that node's link is the one that changes. You can copy the list into an array, or count it and walk again. The classic answer keeps two pointers n links apart, so that when the front one reaches the last node, the back one stands right before the target. Below, L is the number of nodes.

Copy the values into an array

Intuition

In this problem a pointer is a node index. Moving forward is node = next[node], and reaching -1 means you have walked off the end. In the first example the walk from node 0 goes 0 → 2 → 4 → 1 → 3 → -1.

Counting from the end is hard only because a list has no positions. So give it positions: walk once and append each value to an array. For the first example that array is [5, 2, 6, 9, 7]. In an array of L values the last one sits at index L-1, so the n-th from the end sits at index L-n. Here that is 5-2 = 3, the 9. Delete it and return [5, 2, 6, 7].

This is correct and runs in O(L) time, but it copies the whole list and never touches a link. The point of the problem is to edit the list itself, with O(1) extra memory, which is what the next two approaches do.

Algorithm

Start with an empty array and node = 0.
While node is not -1, append values[node] and move to next[node].
Delete the entry at index length - n.
Return the array.

def removeNthFromEnd(values, next, n):
    # Write the values out in list order.
    order = []
    node = 0
    while node != -1:
        order.append(values[node])
        node = next[node]
    # Counting from the end, the n-th value sits at index len(order) - n.
    del order[len(order) - n]
    return order

Count the nodes, then unlink

Intuition

To remove a node from a list, you change the link of the node before it so that it skips over: next[prev] = next[next[prev]]. The removed node is still in the arrays, but no walk from the head ever reaches it again.

So find prev. Count the nodes in a first walk. Counting the head as position 0, the target sits at position L-n and the node before it at L-n-1, which you reach from the head in L-n-1 steps. In the first example L = 5 and n = 2: two steps 0 → 2 → 4 put you on node 4, which links to node 1, the 9. Setting next[4] = next[1] = 3 makes the list read 5, 2, 6, 7.

One case has no node before the target: n = L, when the target is the head. Nothing needs relinking then. The list starts at next[0] instead of 0, as in the second example. Then walk from the head to collect the answer. Two walks over the list cost about 2L moves, and the memory beyond the answer is a few integers.

Algorithm

Walk from node 0 to -1 and count the nodes as L.
If n == L, the new head is next[0].
Otherwise start prev at node 0 and move it L-n-1 times, then set next[prev] = next[next[prev]].
Walk from the head and collect values[node] in order.

def removeNthFromEnd(values, next, n):
    # First pass: count the nodes.
    length = 0
    node = 0
    while node != -1:
        length += 1
        node = next[node]
    head = 0
    if n == length:
        # The node to remove is the head, so the list starts at its second node.
        head = next[0]
    else:
        # Second pass: stop on the node just before position length - n.
        prev = 0
        for _ in range(length - n - 1):
            prev = next[prev]
        next[prev] = next[next[prev]]  # skip over the removed node
    result = []
    node = head
    while node != -1:
        result.append(values[node])
        node = next[node]
    return result

Two pointers n links apart

Intuition

You can measure "n from the end" without knowing L. Move fast n links ahead while slow waits on the head. Then move both one link at a time. The gap stays n, so when fast stands on the last node (next[fast] == -1, position L-1), slow stands at position L-1-n: the node right before the target. One next[slow] = next[next[slow]] cuts the target out.

Follow the first example. fast takes two steps, 0 → 2 → 4. Now both move: slow goes to 2 while fast goes to 1, then slow to 4 while fast goes to 3. Node 3 is the last one, so you stop. next[4] is node 1, the 9, and setting next[4] = next[1] = 3 removes it.

The head case shows up on its own. Since n ≤ L, fast reaches -1 during its head start only when n = L, and that is exactly when the head is the target. With node objects you would put a dummy node in front of the head to make this case disappear; here the check fast == -1 does the same job. Finding and unlinking takes one pass. Writing out the answer is one more walk, which every approach needs.

Algorithm

Set fast = 0 and move it n times with fast = next[fast].
If fast == -1, the head is the target: the new head is next[0].
Otherwise set slow = 0 and move both while next[fast] != -1.
Set next[slow] = next[next[slow]].
Walk from the head and collect values[node] in order.

def removeNthFromEnd(values, next, n):
    # Send fast n links ahead of slow.
    fast = 0
    for _ in range(n):
        fast = next[fast]
    head = 0
    if fast == -1:
        # Fast fell off the end, so the list has exactly n nodes: remove the head.
        head = next[0]
    else:
        # Move both, keeping the gap. When fast stands on the last node,
        # slow stands just before the node to remove.
        slow = 0
        while next[fast] != -1:
            slow = next[slow]
            fast = next[fast]
        next[slow] = next[next[slow]]  # skip over the removed node
    result = []
    node = head
    while node != -1:
        result.append(values[node])
        node = next[node]
    return result

Pitfalls and edge cases

Most wrong answers come from where the follower stops and from the case where the head is removed.

Removing the entry at array index L-n. The nodes are not stored in list order, so that index is usually some other node. In the first example values[3] = 7 is the last node, not the 9.
Stopping when fast == -1 instead of when next[fast] == -1. That moves slow one step too far, onto the target itself, and in a singly linked list you cannot unlink a node from the node itself.
Forgetting the head case. When n = L, fast is -1 after its head start, and reading next[fast] crashes in most languages. Python reads next[-1] without complaint and returns a wrong list, which is harder to spot.
Unlinking with next[slow] = next[slow] + 1 or slow + 2. Neighbours in the list are not neighbours in the arrays; the only way to the node after the target is next[next[slow]].
Collecting the answer from node 0 after the head was removed. Start the final walk at the new head.
Forgetting the offset in Lua and R, where arrays start at 1. Keep node indexes 0-based and read next[node + 1]. Ruby and R reserve the word next, so their starters name the parameter next_.

Frequently asked questions4

How do you remove the nth node from the end of a linked list in one pass?

Use two pointers with a gap of n. Move the first one n nodes ahead, then move both together until the first one is on the last node. The second one now stands right before the node to remove, so you point its link past that node. If the first pointer runs off the list during its head start, the node to remove is the head.

Why do solutions to this problem use a dummy node?

Removing a node means changing the link of the node before it, and the head has no node before it. A dummy node placed in front of the head gives every node, the head included, a predecessor, so one unlinking line covers all cases. The answer then starts at the dummy's next node. Checking whether the leading pointer ran off the list after n steps handles the same case without the extra node.

What is the time and space complexity of removing the nth node from the end?

It takes O(L) time for a list of L nodes, since you have to reach the end to know where the target is. Counting first and the two pointer method both use O(1) extra memory. Copying the values into an array uses O(L).

Is the two pointer solution faster than counting the length first?

Not by much: both are O(L), and the two pointers together still make about as many moves as two walks would. The real gain is that you never need the length up front, so the method also works when the list arrives as a stream you can read only once. That single pass is what interviewers usually ask for.

Python

def removeNthFromEnd(values, next, n):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

values = [5, 9, 2, 7, 6]
next = [2, 3, 4, -1, 1]
n = 2

Expected

[5, 2, 6, 7]

Remove Nth Node From End of List

Function

Constraints

Examples

Hints

Solution

Copy the values into an array

Count the nodes, then unlink

Two pointers n links apart

Pitfalls and edge cases

Frequently asked questions4

Similar problems