Remove Nth Node From End of List

Mediumlinked-listtwo-pointers
Category: Linked List
Companies that ask this question:
AmazonMicrosoftFacebookGoogle
LeetCode →NeetCode →

Approach

Remove Nth Node From End of List

Problem Statement

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

Examples

Example 1

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
Explanation: Remove 4 (2nd from end)

Example 2

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

Example 3

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

Intuition

Challenge: Need to find nth node from END, but linked list only goes forward.

Naive Approach:

  1. Count total length: O(n)
  2. Traverse to (length - n)th node: O(n)
  3. Total: O(n) time, but 2 passes

Optimal Approach: One pass with two pointers

  • Fast pointer moves n steps ahead
  • Then both move together until fast reaches end
  • Slow is now at node BEFORE target
  • Remove slow.next

Pattern Recognition

This is a Two Pointers (Fast/Slow) problem:

  • Create n-node gap between pointers
  • Move together until fast reaches end
  • Slow positioned perfectly to remove target

Approach

# Use dummy node to handle edge case (removing head)
dummy = ListNode(0, head)
slow = fast = dummy

# Move fast n steps ahead
for i in range(n):
    fast = fast.next

# Move both until fast at end
while fast.next:
    slow = slow.next
    fast = fast.next

# Remove target node
slow.next = slow.next.next

return dummy.next

Complexity Analysis

  • Time: O(L) where L is list length

    • Single pass through list
    • Move fast n steps, then both (L-n) steps
    • Total: n + (L-n) = L

  • Space: O(1)

    • Only pointers used
    • No extra data structures

Visual Example

For [1,2,3,4,5], n = 2 (remove 4):

Step 1: Move fast 2 steps ahead
dummy → 1 → 2 → 3 → 4 → 5
slow↑        fast↑

Step 2: Move both until fast at end
dummy → 1 → 2 → 3 → 4 → 5
         slow↑         fast↑

Step 3: Remove slow.next (node 4)
dummy → 1 → 2 → 3 → 5
         slow↑

Result: [1,2,3,5]

Edge Cases

  1. Remove head (n = length): dummy node handles
  2. Single node (n = 1): return null
  3. Remove last node (n = 1): standard case

Solution

java
1/**
2 * Definition for singly-linked list.
3 * public class ListNode {
4 *     int val;
5 *     ListNode next;
6 *     ListNode() {}
7 *     ListNode(int val) { this.val = val; }
8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9 * }
10 */
11
12class Solution {
13    public ListNode removeNthFromEnd(ListNode head, int n) {
14        // Dummy node to handle edge case of removing head
15        ListNode dummy = new ListNode(0, head);
16        ListNode slow = dummy;
17        ListNode fast = dummy;
18
19        // Move fast n steps ahead
20        for (int i = 0; i < n; i++) {
21            fast = fast.next;
22        }
23
24        // Move both until fast at end
25        while (fast.next != null) {
26            slow = slow.next;
27            fast = fast.next;
28        }
29
30        // Remove target node
31        slow.next = slow.next.next;
32
33        return dummy.next;
34    }
35}
36
37
38// Alternative: Two Pass Solution
39class SolutionTwoPass {
40    public ListNode removeNthFromEnd(ListNode head, int n) {
41        // Count length
42        int length = 0;
43        ListNode curr = head;
44        while (curr != null) {
45            length++;
46            curr = curr.next;
47        }
48
49        // Edge case: remove head
50        if (n == length) {
51            return head.next;
52        }
53
54        // Find node before target
55        curr = head;
56        for (int i = 0; i < length - n - 1; i++) {
57            curr = curr.next;
58        }
59
60        // Remove target
61        curr.next = curr.next.next;
62
63        return head;
64    }
65}
66
Loading visualizer...