Remove Nth Node From End of List

medium
Linked ListLinked ListTwo Pointers

Given the head of a linked list, remove the nth node from the end of the list and return its head. The given n will always be valid.

Examples

Example 1

  • Input: head = [1,2,3,4,5], n = 2
  • Output: [1,2,3,5]
  • Explanation: The 2nd node from the end is 4. After removing it, the list becomes [1,2,3,5].

Example 2

  • Input: head = [1], n = 1
  • Output: []
  • Explanation: The only node is removed, resulting in an empty list.

Example 3

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

Constraints

  • The number of nodes in the list is sz.
  • 1 <= sz <= 30
  • 0 <= Node.val <= 100
  • 1 <= n <= sz

Approaches

2 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Two Pass

Intuition

The straightforward approach is to first calculate the total length of the list, then determine the position of the node to remove from the beginning. The node to remove is at position length - n from the start (0-indexed). We traverse again to the node just before that position and adjust the pointers to skip the target node. A dummy node simplifies edge cases such as removing the head.

Algorithm

  1. Traverse the list once to calculate its total length.
  2. Create a dummy node pointing to `head`.
  3. Compute the position from the start: `length - n`.
  4. Traverse from the dummy node to the node just before position `length - n`.
  5. Set that node's `next` to `next.next`, skipping the target node.
  6. Return `dummy.next`.
TimeO(n)SpaceO(1)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        int length = 0;
        ListNode* curr = head;
        while (curr != nullptr) {
            length++;
            curr = curr->next;
        }

        ListNode dummy(0, head);
        curr = &dummy;
        for (int i = 0; i < length - n; i++) {
            curr = curr->next;
        }
        curr->next = curr->next->next;

        return dummy.next;
    }
};
Java 21
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int length = 0;
        ListNode curr = head;
        while (curr != null) {
            length++;
            curr = curr.next;
        }

        ListNode dummy = new ListNode(0, head);
        curr = dummy;
        for (int i = 0; i < length - n; i++) {
            curr = curr.next;
        }
        curr.next = curr.next.next;

        return dummy.next;
    }
}
Python 3.12
def removeNthFromEnd(head: Optional[ListNode], n: int) -> Optional[ListNode]:
    length = 0
    curr = head
    while curr:
        length += 1
        curr = curr.next

    dummy = ListNode(0, head)
    curr = dummy
    for _ in range(length - n):
        curr = curr.next
    curr.next = curr.next.next

    return dummy.next
Go 1.26
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    length := 0
    curr := head
    for curr != nil {
        length++
        curr = curr.Next
    }

    dummy := &ListNode{Next: head}
    curr = dummy
    for i := 0; i < length-n; i++ {
        curr = curr.Next
    }
    curr.Next = curr.Next.Next

    return dummy.Next
}
Approach 2

One Pass (Two Pointers)

Intuition

We can solve this in a single pass using two pointers separated by a gap of n nodes. First, advance the fast pointer n steps ahead. Then move both slow and fast one step at a time until fast reaches the end. At that point, slow is right before the node to remove. This works because the distance between slow and fast is always n, so when fast is at the end, slow is n positions from the end. Using a dummy node handles the edge case where the head itself needs to be removed.

Algorithm

  1. Create a dummy node pointing to `head`. Set both `slow` and `fast` to the dummy node.
  2. Advance `fast` by `n + 1` steps so there is a gap of `n` nodes between `slow` and `fast`.
  3. Move both `slow` and `fast` forward one step at a time until `fast` is null.
  4. `slow.next` is the node to remove. Set `slow.next = slow.next.next`.
  5. Return `dummy.next`.
TimeO(n)SpaceO(1)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode dummy(0, head);
        ListNode* slow = &dummy;
        ListNode* fast = &dummy;

        for (int i = 0; i <= n; i++) {
            fast = fast->next;
        }

        while (fast != nullptr) {
            slow = slow->next;
            fast = fast->next;
        }

        slow->next = slow->next->next;

        return dummy.next;
    }
};
Java 21
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 != null) {
            slow = slow.next;
            fast = fast.next;
        }

        slow.next = slow.next.next;

        return dummy.next;
    }
}
Python 3.12
def removeNthFromEnd(head: Optional[ListNode], n: int) -> Optional[ListNode]:
    dummy = ListNode(0, head)
    slow = dummy
    fast = dummy

    for _ in range(n + 1):
        fast = fast.next

    while fast:
        slow = slow.next
        fast = fast.next

    slow.next = slow.next.next

    return dummy.next
Go 1.26
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{Next: head}
    slow := dummy
    fast := dummy

    for i := 0; i <= n; i++ {
        fast = fast.Next
    }

    for fast != nil {
        slow = slow.Next
        fast = fast.Next
    }

    slow.Next = slow.Next.Next

    return dummy.Next
}

Frequently asked questions

What is the optimal time complexity of Remove Nth Node From End of List?

The most efficient approach in this guide ("One Pass (Two Pointers)") runs in O(n) time and uses O(1) extra space. Earlier brute-force approaches are slower; see all 2 approaches above for the full progression.

What pattern does Remove Nth Node From End of List use?

Remove Nth Node From End of List is a medium-level Linked List problem involving Linked List, Two Pointers. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Remove Nth Node From End of List be solved without extra space?

The most space-efficient approach in this guide uses O(1) extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(1), while the optimized version uses O(1).

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Original problem: leetcode.com

Loading editor...
Input
head=
[1,2,3,4,5]
n=
2
Expected Output
[1,2,3,5]