Solving Remove Nth Node From End in JavaScript: Step-by-Step Guide

Introduction to Remove Nth Node From End

The "Remove Nth Node From End of List" problem is one of the most classic linked list challenges you'll encounter in coding interviews and algorithm practice. Given the head of a singly linked list and an integer n, your task is to remove the nth node from the end of the list and return the updated head. While the problem sounds straightforward, it tests your understanding of linked list traversal, pointer manipulation, and edge case handling.

What Is a Singly Linked List?

Before diving into the solution, let's quickly recap what a singly linked list is. A linked list is a linear data structure where elements are stored in nodes. Each node contains two things: a value and a reference (or pointer) to the next node in the sequence. Unlike arrays, linked lists do not store elements in contiguous memory locations, which makes insertion and deletion operations more efficient in certain scenarios.

Here's how a typical linked list node is defined in JavaScript:

class ListNode {
  constructor(val = 0, next = null) {
    this.val = val;
    this.next = next;
  }
}

Why This Problem Matters

You might wonder why removing a node from the end of a linked list is such an important problem. The answer lies in what it teaches you about algorithm design and optimization. This problem forces you to think about:

• Two-pointer techniques: A fundamental pattern used across many algorithmic problems.
• Edge case handling: What happens when the list has only one node? What if n equals the length of the list?
• Space and time optimization: Moving from a naive two-pass solution to an elegant one-pass solution.
• Dummy node pattern: A technique to simplify edge cases when modifying the head of a list.

Mastering this problem builds a strong foundation for tackling more complex linked list problems such as detecting cycles, merging sorted lists, and reversing portions of a list.

Understanding the Problem Statement

Let's break down the problem with a concrete example. Suppose we have the following linked list:

1 -> 2 -> 3 -> 4 -> 5

If n = 2, we need to remove the 2nd node from the end, which is the node with value 4. The resulting list should be:

1 -> 2 -> 3 -> 5

The key insight here is that "from the end" means we're counting backwards. The last node is the 1st from the end, the second-to-last is the 2nd from the end, and so on.

Constraints to Consider

• The number of nodes in the list is in the range [1, 30].
• Node values are between 0 and 100.
• n is a valid positive integer between 1 and the length of the list.

Approach 1: Two-Pass Solution

The most intuitive approach is to traverse the list twice. In the first pass, we calculate the total length of the list. Once we know the length, we can determine which node to remove. If the list has L nodes, the node we want to remove is at position L - n from the beginning (0-indexed). In the second pass, we traverse to that position and remove the node.

Step-by-Step Breakdown

Here's how the two-pass approach works:

• Traverse the entire list to count the number of nodes, storing the count in a variable length.
• Calculate the position from the start: positionToRemove = length - n.
• Use a dummy node pointing to the head to handle the case where we need to remove the head itself.
• Traverse from the dummy node to positionToRemove - 1, which lands us on the node just before the one to remove.
• Update the next pointer to skip over the target node.

Implementation

function removeNthFromEndTwoPass(head, n) {
  // Create a dummy node that points to the head
  const dummy = new ListNode(0);
  dummy.next = head;
  
  // First pass: calculate the length of the list
  let length = 0;
  let current = head;
  while (current !== null) {
    length++;
    current = current.next;
  }
  
  // Calculate the position from the start (0-indexed)
  const positionToRemove = length - n;
  
  // Second pass: traverse to the node just before the one to remove
  current = dummy;
  for (let i = 0; i < positionToRemove; i++) {
    current = current.next;
  }
  
  // Remove the target node by skipping it
  current.next = current.next.next;
  
  // Return the new head (dummy.next handles the case where head was removed)
  return dummy.next;
}

Complexity Analysis

The two-pass solution has a time complexity of O(L), where L is the length of the list, because we traverse the list twice. The space complexity is O(1) since we only use a constant amount of extra space. While this solution works, we can do better by reducing it to a single pass.

Approach 2: One-Pass Two-Pointer Solution

The optimal solution uses the two-pointer technique, also known as the fast and slow pointer approach. The idea is to maintain two pointers that are separated by exactly n nodes. When the fast pointer reaches the end of the list, the slow pointer will be positioned just before the node we need to remove.

How the Two-Pointer Technique Works

Imagine you have two runners on a track. The fast runner starts n steps ahead of the slow runner. When the fast runner reaches the finish line (the end of the list), the slow runner is exactly n steps behind, which means the slow runner is at the node just before the one we want to remove.

Here's the detailed algorithm:

• Create a dummy node and set its next pointer to the head of the list.
• Initialize both fast and slow pointers to point to the dummy node.
• Move the fast pointer n + 1 steps ahead. This creates a gap of n nodes between fast and slow.
• Move both fast and slow pointers forward one step at a time until fast reaches null.
• At this point, slow is pointing to the node just before the one to remove.
• Update slow.next to skip over the target node.
• Return dummy.next as the new head.

Implementation

function removeNthFromEnd(head, n) {
  // Create a dummy node to handle edge cases cleanly
  const dummy = new ListNode(0);
  dummy.next = head;
  
  // Initialize both pointers at the dummy node
  let fast = dummy;
  let slow = dummy;
  
  // Move fast pointer n+1 steps ahead to create a gap of n
  for (let i = 0; i <= n; i++) {
    fast = fast.next;
  }
  
  // Move both pointers until fast reaches the end
  while (fast !== null) {
    fast = fast.next;
    slow = slow.next;
  }
  
  // Remove the target node
  slow.next = slow.next.next;
  
  // Return the new head
  return dummy.next;
}

Tracing Through an Example

Let's trace through the example with the list 1 -> 2 -> 3 -> 4 -> 5 and n = 2:

Initial state:
dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
fast = dummy, slow = dummy

After moving fast n+1 = 3 steps:
dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
              fast
slow

After first iteration of while loop:
dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
                   fast
       slow

After second iteration:
dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
                        fast
            slow

After third iteration (fast is now null):
dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
                             fast (null)
                slow

slow.next (node 4) is removed:
slow.next = slow.next.next
Result: 1 -> 2 -> 3 -> 5 -> null

Complexity Analysis

The one-pass solution has a time complexity of O(L), where L is the length of the list. Although the asymptotic complexity is the same as the two-pass solution, this approach is more efficient in practice because it only traverses the list once. The space complexity remains O(1) since we only use a fixed number of pointers.

Handling Edge Cases

Edge cases are where many solutions fail. Let's examine the critical edge cases you need to handle:

Single Node List

When the list contains only one node and n = 1, removing that node results in an empty list. The dummy node pattern handles this gracefully because dummy.next will point to null after the removal.

// List: 1 -> null, n = 1
// After removal: null

Removing the Head Node

When n equals the length of the list, we need to remove the head node. Without the dummy node, this would require special handling because there's no previous node to update. The dummy node solves this by acting as a virtual predecessor to the head.

// List: 1 -> 2 -> 3 -> null, n = 3
// We need to remove node 1 (the head)
// Result: 2 -> 3 -> null

Removing the Last Node

When n = 1, we remove the last node in the list. This is the simplest case because the slow pointer will land on the second-to-last node, and we simply set its next pointer to null.

// List: 1 -> 2 -> 3 -> null, n = 1
// We need to remove node 3 (the tail)
// Result: 1 -> 2 -> null

Testing Your Solution

To ensure your solution is correct, you should test it against various scenarios. Here's a helper function to create a linked list from an array and another to convert it back to an array for easy verification:

// Helper function to create a linked list from an array
function createList(arr) {
  if (arr.length === 0) return null;
  const head = new ListNode(arr[0]);
  let current = head;
  for (let i = 1; i < arr.length; i++) {
    current.next = new ListNode(arr[i]);
    current = current.next;
  }
  return head;
}

// Helper function to convert a linked list to an array
function listToArray(head) {
  const result = [];
  let current = head;
  while (current !== null) {
    result.push(current.val);
    current = current.next;
  }
  return result;
}

// Test cases
function runTests() {
  // Test 1: Normal case
  let list1 = createList([1, 2, 3, 4, 5]);
  let result1 = removeNthFromEnd(list1, 2);
  console.log(listToArray(result1)); // Expected: [1, 2, 3, 5]
  
  // Test 2: Single node
  let list2 = createList([1]);
  let result2 = removeNthFromEnd(list2, 1);
  console.log(listToArray(result2)); // Expected: []
  
  // Test 3: Remove head
  let list3 = createList([1, 2, 3]);
  let result3 = removeNthFromEnd(list3, 3);
  console.log(listToArray(result3)); // Expected: [2, 3]
  
  // Test 4: Remove tail
  let list4 = createList([1, 2, 3]);
  let result4 = removeNthFromEnd(list4, 1);
  console.log(listToArray(result4)); // Expected: [1, 2]
  
  // Test 5: Two nodes, remove first
  let list5 = createList([1, 2]);
  let result5 = removeNthFromEnd(list5, 2);
  console.log(listToArray(result5)); // Expected: [2]
}

runTests();

Best Practices

When solving linked list problems like this one, following best practices will help you write cleaner, more maintainable code:

• Always use a dummy node: The dummy node pattern simplifies edge case handling, especially when the head of the list might be modified or removed. It eliminates the need for special conditional logic to handle head removal.
• Draw the problem: Before writing code, sketch the linked list and trace through your algorithm on paper. This helps you visualize pointer movements and catch logic errors early.
• Check for null pointers: Always verify that pointers are not null before accessing their properties. While the problem constraints guarantee valid input, defensive programming is a good habit.
• Prefer one-pass solutions: When a problem can be solved in one pass instead of two, the one-pass solution is generally preferred, even if the asymptotic complexity is the same. It demonstrates deeper algorithmic thinking.
• Write comprehensive tests: Test your solution with edge cases, including single-node lists, head removal, tail removal, and lists of various sizes. This builds confidence in your implementation.
• Comment your code: Explain the purpose of each step, especially the non-obvious ones like moving the fast pointer n + 1 steps ahead. This makes your code easier to understand and maintain.

Common Mistakes to Avoid

Even experienced developers make mistakes when working with linked lists. Here are some common pitfalls:

• Forgetting the dummy node: Without a dummy node, removing the head requires special handling that often leads to bugs or null reference errors.
• Off-by-one errors: Moving the fast pointer n steps instead of n + 1 steps is a common mistake. Remember, you want the slow pointer to land on the node before the one to remove, not on the node to remove itself.
• Not returning the correct head: Always return dummy.next instead of head, because the original head might have been removed.
• Modifying the list incorrectly: Make sure you update slow.next = slow.next.next and not slow = slow.next.next. The former modifies the list structure; the latter just moves a local pointer.

Conclusion

The Remove Nth Node From End problem is an excellent exercise in linked list manipulation and two-pointer techniques. By using a dummy node and the fast-slow pointer approach, you can solve this problem efficiently in a single pass with O(L) time complexity and O(1) space complexity. The dummy node pattern is particularly valuable as it elegantly handles the tricky edge case of removing the head node. As you continue practicing linked list problems, you'll find that the patterns and techniques learned here—especially the two-pointer approach and dummy node strategy—will serve as building blocks for solving more complex challenges. Remember to always trace through your algorithm with examples, test edge cases thoroughly, and prioritize clean, well-commented code that clearly communicates your intent to other developers.