Problem Overview

We are given the head of a singly linked list. We are given a node index n from the end.

The goal is to remove the nth node from the end of the list.

Constraints

  • We have to do this in a single pass.

Leetcode - Linked List Cycle

Brute Force Approach

Intuition

  • We use a vector to keep track of the nodes and their indices.
  • Once the traversal is finished, we calculate the node index from the start.
  • Once we get that index, we remove that node.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {

        vector<ListNode*> arr;
        ListNode* curr = head;

        while (curr) {
            arr.push_back(curr);
            curr = curr->next;
        }

        int nodeFromStart = arr.size() - n;

        if (nodeFromStart == 0)
            return head->next;
            
        if (nodeFromStart < arr.size())
            arr[nodeFromStart - 1]->next = arr[nodeFromStart]->next;

        return head;
    }
};

Why This Fails

  • It usegs extra space O(n).
  • The problem requires a constant space solution.

Time and Space Complexity

  • Time: O(n)
  • Space: O(n)

Optimal Approach

We maintain two pointers similar to Floyd’s Tortoise and Hare technique.

  • The fast pointer moves n + 1 steps ahead.
  • Then both fast and slow move together.
  • This maintains a constant gap of n between them.
  • When fast reaches NULL, slow will be just before the node to remove.

Edge Cases

  • Introduce a dummy node before the linked list.
  • If we have to remove the head, this makes handling easier.
  • Without a dummy node, removing the head becomes tricky.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {

        ListNode* dummy = new ListNode(0);
        dummy->next = head;

        ListNode* fast = dummy;
        ListNode* slow = dummy;

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

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

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

        return dummy->next;
    }
};

Time and Space Complexity

  • Time: O(n)
  • Space: O(1)

Key Takeaways

  • Adding a dummy node before the linked list helps simplify edge cases.
  • Maintaining a fixed gap between two pointers is a powerful technique.
  • Two-pointer gap method is very common in single-pass linked list problems.
  • Always think about edge cases like removing the head.