Course4all
Join us on telegram
Home/dsa/Linked List Patterns/Remove Nth Node From End of List

Remove Nth Node From End of List

Master this topic with zero to advance depth.

Remove Nth Node From End of List

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

Visual Representation

List: 1 -> 2 -> 3 -> 4 -> 5, n = 2 Step 1: Move Fast pointer n=2 steps ahead. Dummy -> 1 -> 2 -> 3 -> 4 -> 5 S F Step 2: Move both S and F until F reaches the end. Dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null S F Step 3: S.next = S.next.next (Removes 4) 1 -> 2 -> 3 -> 5
Medium

Examples

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

The second node from the end is 4. Removing it results in [1,2,3,5].

Approach 1

Level I: Two Pass (Length Calculation)

Intuition

To remove the n^{th} node from the end, we calculate the total length L of the list. The node to remove is at index (L - n) from the start (0-indexed if using a dummy node).

⏱ O(L)💾 O(1)

Detailed Dry Run

Input: 1->2->3->4->5, n=2. Length = 5. Target to skip: 5 - 2 = 3 steps from dummy.

StepsCurrAction
0DummyMove
11Move
22Move
33Stop. curr is now at node 3. curr.next (node 4) is the one to remove.
curr.next = curr.next.next (node 3 points to node 5)
java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        int length = 0;
        ListNode first = head;
        while (first != null) {
            length++;
            first = first.next;
        }
        length -= n;
        first = dummy;
        while (length > 0) {
            length--;
            first = first.next;
        }
        first.next = first.next.next;
        return dummy.next;
    }
}

⚠️ Common Pitfalls & Tips

You must handle the case where the head itself is removed. Using a dummy node simplifies this.

Approach 2

Level II: Better (Recursion)

Intuition

We can solve this problem recursively by traversing to the end of the list and then backtracking. During backtracking, we keep track of the node count from the end. When it reaches n, we remove the next node.

  1. Recursively call the function for head.next.
  2. On return, increment a counter.
  3. If counter equals n, the current node's next should be skipped.
⏱ O(L)💾 O(L) (recursion stack)

Detailed Dry Run

Input: 1->2->3, n=1

  1. Push 1, 2, 3 to stack.
  2. Pop 3, count=1. count == n, so return to 2 acknowledging 3 should be removed? (Actually implementation differs slightly).
java
class Solution {
    int count = 0;
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) return null;
        head.next = removeNthFromEnd(head.next, n);
        count++;
        if (count == n) return head.next;
        return head;
    }
}

⚠️ Common Pitfalls & Tips

O(L) space due to recursion might be an issue for very long lists.

Approach 3

Level III: Optimal (One Pass - Two Pointers)

Intuition

Use two pointers, fast and slow. Move fast n steps ahead. Then move both until fast reaches the end. slow will now be just before the node to be removed.

  1. Initialize fast and slow pointers at a dummy node.
  2. Move the fast pointer n+1 steps forward.
  3. Move both pointers together until the fast pointer reaches the end (null).
  4. At this point, slow.next is the node to be removed. Update slow.next = slow.next.next.
⏱ O(L)💾 O(1)

Detailed Dry Run

Input: 1->2->3->4->5, n=2

  1. Start fast, slow at dummy.
  2. Move fast 3 steps: fast points at 3.
  3. Move both: fast at 4, slow at 1; fast at 5, slow at 2; fast at null, slow at 3.
  4. slow.next (node 4) is removed.
java
public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode fast = dummy, slow = dummy;
    for (int i = 0; i <= n; i++) fast = fast.next;
    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }
    slow.next = slow.next.next;
    return dummy.next;
}

⚠️ Common Pitfalls & Tips

The gap between fast and slow must be exactly n+1 to land 'slow' on the node before the target.

Visual Representation

List: 1 -> 2 -> 3 -> 4 -> 5, n = 2 [D] -> [1] -> [2] -> [3] -> [4] -> [5] -> null S,F 1. Move Fast 3 steps (n+1): [D] -> [1] -> [2] -> [3] -> [4] -> [5] S F 2. Move both until F is null: [D] -> [1] -> [2] -> [3] -> [4] -> [5] -> null S F 3. S.next = S.next.next (skip 4): [3] -> [5]
← Previous QuestionLinked List Cycle
Next Question →Partition List