Remove Nth Node From End of List

The problem

You are given the head of a singly linked list and a number position_from_end. Remove the node at that position, counting from the end of the list, and return the head. The last node is at position 1.

Example 1

Input: head = [8, 3, 6, 2, 9, 5], position_from_end = 2

Output: [8, 3, 6, 2, 5]

Counting from the end, 5 is 1st and 9 is 2nd. So 9 goes, and 2 now links straight to 5.

Example 2

Input: head = [4], position_from_end = 1

Output: []

The only node is removed, so the list is empty.

Example 3

Input: head = [1, 7], position_from_end = 2

Output: [7]

The 2nd from the end is the head itself. The new head is 7.

Constraints

• 1 ≤ L ≤ 30, where L is the number of nodes
• 0 ≤ Node.val ≤ 100
• 1 ≤ position_from_end ≤ L. Below, n is position_from_end.

Clarifying questions

Is position_from_end always valid?

Yes. 1 ≤ position_from_end ≤ L, so the node always exists.

Can the head be the node to remove?

Yes, when n = L. Then the answer starts at the second node.

Do we know the length?

No. We only get the head. Finding the length costs a full pass.

Can it be done in one pass?

Yes. That is the follow-up, and the two-pointer answer does it.

Spot the pattern

“n-th from the end” is easy to turn into “k-th from the front” once you know the length. To skip the counting pass, keep two pointers a fixed distance apart. When the front one reaches the end, the back one is exactly where we need it. This is the two pointers pattern on a linked list.

Solutions

Count, then walkO(L), two passesTwo pointersO(L), one pass

Show all

This problem has two approaches. Both are O(L), and the second one needs only one pass.

Count, then walk O(L), two passes

The idea

Walk the whole list once to count its length L. The node to remove is number L − n + 1 from the front. To unlink it, we stand on the node before it and point that node past it. That node is L − n steps from a dummy node placed in front of the head.

The dummy node handles the case where the head itself must go: then we take 0 steps, and the dummy is the node before it.

Walkthrough

length

0

1. length, node = 0, head
2. while node: length += 1; node = node.next
3. dummy = ListNode(0, head)
4. previous = dummy
5. for _ in range(length - position_from_end):
6. previous = previous.next
7. previous.next = previous.next.next
8. return dummy.next

Pass 1 counts the nodes. Then the node to remove is number L − 2 + 1 from the front.

← BackStep →Play1 / 14

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Count, then walk: find the length L, then step to the node before the
    // one to remove. Two passes, O(L) time and O(1) memory.
    public ListNode removeNthFromEnd(ListNode head, int positionFromEnd) {
        int length = 0;
        for (ListNode node = head; node != null; node = node.next) length++;
        // A dummy in front gives even the head a node before it.
        ListNode dummy = new ListNode(0, head);
        ListNode previous = dummy;
        // The target is node length - positionFromEnd + 1, so the node before it
        // is length - positionFromEnd steps from dummy.
        for (int i = 0; i < length - positionFromEnd; i++) previous = previous.next;
        previous.next = previous.next.next;
        return dummy.next;
    }
}

Big O

Time O(L)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   Two loops run one after the other. The first counts one node per run. The second moves previous one node per run. Both are 1 step.

   1. length, node = 0, head
   2. while node: length += 1; node = node.next
   3. dummy = ListNode(0, head)
   4. previous = dummy
   5. for _ in range(length - position_from_end):
   6. previous = previous.next
   7. previous.next = previous.next.next
   8. return dummy.next

2. 2 Count the runs on Example 1

   Example 1 has 6 nodes and n = 2. Counting takes 6 runs. Walking takes 6 − 2 = 4 runs.

   6 + 4 = 10 runs.

   loop	count	walk
   runs	6	4

   total

   6 + 4 = 10

3. 3 Write the count for any n

   L + (L − n) = 2L − n

   Check it with Example 1: 2 × 6 − 2 = 10. The worst case is n = 1, which is 2L − 1.

4. 4 Keep only the part that grows fastest

   Drop the 2 and the − n. What is left is L.

   So the time is O(L).

5. S Space: count the extra memory the same way

   The code keeps length, node, dummy and previous. That is fixed, for any L, so the space is O(1).

   lengthnodedummyprevious

Two pointers O(L), one pass

The idea

Start slow and fast on a dummy node in front of the head. Move fast n + 1 nodes ahead. Then move both, one node at a time, until fast falls off the end (becomes null).

The gap between them never changes: it stays n + 1. When fast is null, it is one step past the last node. So slow is n + 1 steps before null, which is the node just before the one to remove. Point slow.next past it.

The invariant: fast is always exactly n + 1 nodes after slow.

Walkthrough

1. dummy = ListNode(0, head)
2. slow = fast = dummy
3. for _ in range(position_from_end + 1):
4. fast = fast.next
5. while fast:
6. slow, fast = slow.next, fast.next
7. slow.next = slow.next.next
8. return dummy.next

Both pointers start on the dummy node D. First, fast runs 3 nodes ahead.

← BackStep →Play1 / 10

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Two pointers: keep fast positionFromEnd + 1 nodes ahead of slow. When fast is
    // null, slow is right before the node to remove. One pass, O(L) time, O(1) memory.
    public ListNode removeNthFromEnd(ListNode head, int positionFromEnd) {
        // A dummy in front gives even the head a node before it.
        ListNode dummy = new ListNode(0, head);
        ListNode slow = dummy, fast = dummy;
        for (int i = 0; i <= positionFromEnd; i++) fast = fast.next;
        // The gap stays positionFromEnd + 1, so slow stops that many nodes before null.
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
}

Big O

Time O(L)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The first loop moves fast once per run. The second moves both pointers once per run. Each run is 1 step. The loops run one after the other.

   1. dummy = ListNode(0, head)
   2. slow = fast = dummy
   3. for _ in range(position_from_end + 1):
   4. fast = fast.next
   5. while fast:
   6. slow, fast = slow.next, fast.next
   7. slow.next = slow.next.next
   8. return dummy.next

2. 2 Count the runs on Example 1

   Example 1 has 6 nodes and n = 2. fast first moves 3 nodes ahead. Then both move 4 times, until fast is null.

   3 + 4 = 7 runs.

   loop	fast ahead	both move
   runs	3	4

   total

   3 + 4 = 7

3. 3 Write the count for any n

   fast starts on the dummy and ends on null. That is L + 1 moves in total, split between the two loops:

   (n + 1) + (L − n) = L + 1

   Check it with Example 1: 6 + 1 = 7.

4. 4 Keep only the part that grows fastest

   Drop the + 1. What is left is L. It is the same Big O as counting first, but done in one pass.

   So the time is O(L).

5. S Space: count the extra memory the same way

   The code keeps dummy, slow and fast. The space is O(1).

   dummyslowfast

Common mistake

Starting without a dummy node

If both pointers start on the head, removing the head itself (n = L) has no node before it, and fast runs off the end too early. The dummy node gives every real node a node before it, so there is no special case.

Tested at the limits

2,000 random lists of 1 to 8 nodes, removing any position from the tail to the head. Count, then walk and the two pointers gave the same list every time.

Largest inputs	Result
30 nodes (the most allowed), removing each of the 30 positions in turn, the head included. Both approaches.	Under 0.001 s each, and under 0.001 MB of extra memory: one dummy node and two pointers.