Remove Nth Node From End of List

Medium Problem 54 of 151 Java and Python

Practice on LeetCode

Problem

Given the head of a linked list, remove the n-th node from the end of the list and return its head.

Example 1

Input: head = [1, 2, 3, 4, 5], n = 2
Output: [1, 2, 3, 5]
Why: The 2nd node from the end is 4.

Example 2

Input: head = [1], n = 1
Output: []

Example 3

Input: head = [1, 2], n = 1
Output: [1]

Constraints

1 ≤ size ≤ 30
1 ≤ n ≤ size

Explanation

Moving a pointer n steps ahead of another one, and then moving both until the leader hits the end, leaves the follower exactly n nodes from the end.

To delete a node you need the node before it. Starting both pointers at a dummy node in front of the head gives you that, and also handles deleting the head itself.

Approach 1 · Naive

Two passes with the length

Time O(L), two passes
Space O(1)

Count the nodes, then walk to the node just before position length - n and unlink the next one.

Count the length L.
From a dummy head, walk L - n steps to the node before the target.
Set node.next = node.next.next.

Java

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int length = 0;
        for (ListNode node = head; node != null; node = node.next) {
            length++;
        }
        ListNode dummy = new ListNode(0, head);
        ListNode node = dummy;
        for (int i = 0; i < length - n; i++) {
            node = node.next;
        }
        node.next = node.next.next;
        return dummy.next;
    }
}

Python

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        length, node = 0, head
        while node:
            length += 1
            node = node.next
        dummy = ListNode(0, head)
        node = dummy
        for _ in range(length - n):
            node = node.next
        node.next = node.next.next
        return dummy.next

Approach 2 · Optimal

One pass with a gap of n

Time O(L), one pass
Space O(1)

Move fast n steps ahead, then move fast and slow together until fast is at the last node. slow is then just before the target.

Set slow = fast = dummy.
Move fast forward n times.
While fast.next: move both.
Unlink slow.next; return dummy.next.

Java

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode slow = dummy;
        ListNode fast = dummy;
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
}

Python

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        slow = fast = dummy
        for _ in range(n):
            fast = fast.next
        while fast.next:
            slow, fast = slow.next, fast.next
        slow.next = slow.next.next
        return dummy.next

Complexity compared

Approach	Time	Space
Naive Two passes with the length	O(L), two passes	O(1)
Optimal One pass with a gap of n	O(L), one pass	O(1)

Key takeaways

A dummy node makes "remove the head" the same as any other removal.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem