Remove Nth Node From End of List

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 make about as many moves as two walks. The gain is that you never need the length up front, so the method also works on a list you can read only once.

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, the list reads 5, 2, 6, 9, 7. The 2nd from the end is the 9, at node 1; removing it leaves 5, 2, 6, 7.

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 [].

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 counted from the end, but a singly linked list only walks forward, and to unlink a node you must stand on the node before it. Keep two pointers n links apart: 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

A pointer here is a node index, and moving forward is node = next[node]. Walk once and append each value to an array: [5, 2, 6, 9, 7] in the first example. The n-th from the end sits at index L-n, here 5-2 = 3, the 9. Delete it and return the rest.

It runs in O(L) time and O(L) extra memory, and it never edits a link.

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, point the link of the node before it past it: next[prev] = next[next[prev]]. Count the nodes in a first walk. With the head at position 0, the target is at position L-n, so prev is L-n-1 steps from the head. In the first example two steps 0 → 2 → 4 reach node 4, and next[4] = next[1] = 3 cuts out the 9.

When n = L the target is the head, which has no node before it, so the list starts at next[0] instead, as in the second example. Two walks cost about 2L moves and a few integers of memory.

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

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 is on the last node (position L-1), slow is at position L-1-n, right before the target. You never need L.

In the first example fast goes 0 → 2 → 4. Then slow moves to 2 and 4 while fast moves to 1 and 3, the last node, and next[4] = next[1] = 3 removes the 9.

Since n ≤ L, fast reaches -1 during its head start only when n = L, exactly when the head is the target. That check does the job a dummy node does with node objects.

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

Removing the entry at array index L-n. The nodes are not stored in list order: in the first example values[3] = 7 is the last node, not the 9.
Moving both pointers until fast == -1 instead of next[fast] == -1. slow then lands on the target itself, and a node cannot unlink itself.
Forgetting the head case. When n = L, fast is -1 after its head start and reading next[fast] crashes. Python reads next[-1] silently and returns a wrong list.
Collecting the answer from node 0 after the head was removed. Start the final walk at the new head.
In Lua and R arrays start at 1. Keep node indexes 0-based and read next[node + 1].

Frequently asked questions3

Why do solutions to this problem use a dummy node?

Removing a node changes the link of the node before it, and the head has none. A dummy node in front of the head gives every node a predecessor, so one unlinking line covers every case, and the answer starts at the dummy's next node. Checking whether the leading pointer ran off the list does the same job without it.

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 make about as many moves as two walks. The gain is that you never need the length up front, so the method also works on a list you can read only once.

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

Test #1

Test #2

Test #3

Arguments

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

Expected Output

[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 questions3

Similar problems