Remove Nth Node from End of List in DSA Javascript

Mental Model

To remove the Nth node from the end, we find the node just before it by moving two pointers with a gap of N nodes.

Analogy: Imagine two friends walking on a path where one starts N steps ahead. When the front friend reaches the end, the other is right before the target to remove.

head -> 1 -> 2 -> 3 -> 4 -> 5 -> null
          ↑
         slow
                 ↑
                fast

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> 4 -> 5, remove 2nd node from end

Goal: Remove the 4 (2nd node from end) and link 3 directly to 5

Step 1: Move fast pointer 2 steps ahead

head -> 1 -> 2 -> 3 -> 4 -> 5 -> null
                 ↑
                fast
          ↑
         slow

Why: Create a gap of 2 nodes between fast and slow pointers

Step 2: Move both slow and fast pointers one step until fast reaches end

head -> 1 -> 2 -> 3 -> 4 -> 5 -> null
                      ↑
                     fast
                 ↑
                slow

Why: Keep the gap so slow will be just before the node to remove

Step 3: Move both pointers one more step

head -> 1 -> 2 -> 3 -> 4 -> 5 -> null
                           ↑
                          fast
                      ↑
                     slow

Why: fast reached the last node, slow is before target node

Step 4: Remove node after slow by linking slow.next to slow.next.next

head -> 1 -> 2 -> 3 -> 5 -> null
                      ↑
                     slow

Why: Skip the 4th node to remove it from the list

Result:

head -> 1 -> 2 -> 3 -> 5 -> null

Annotated Code

DSA Javascript

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

function removeNthFromEnd(head, n) {
  const dummy = new ListNode(0, head); // dummy node before head
  let slow = dummy;
  let fast = dummy;

  // Move fast pointer n steps ahead
  for (let i = 0; i < n; i++) {
    fast = fast.next;
  }

  // Move both pointers until fast reaches the end
  while (fast.next !== null) {
    slow = slow.next;
    fast = fast.next;
  }

  // Remove the nth node from end
  slow.next = slow.next.next;

  return dummy.next;
}

// Driver code
const head = new ListNode(1,
  new ListNode(2,
    new ListNode(3,
      new ListNode(4,
        new ListNode(5)))));
const n = 2;

const newHead = removeNthFromEnd(head, n);

// Print list
let curr = newHead;
let result = '';
while (curr !== null) {
  result += curr.val + ' -> ';
  curr = curr.next;
}
result += 'null';
console.log(result);

const dummy = new ListNode(0, head); // dummy node before head

Create dummy node to handle edge cases like removing head

for (let i = 0; i < n; i++) { fast = fast.next; }

Advance fast pointer n steps ahead to create gap

while (fast.next !== null) { slow = slow.next; fast = fast.next; }

Move both pointers until fast reaches last node

slow.next = slow.next.next;

Remove target node by skipping it

Output

1 -> 2 -> 3 -> 5 -> null

Complexity Analysis

Time: O(n) because we traverse the list once with two pointers

Space: O(1) because we use only a few pointers, no extra data structures

vs Alternative: Naive approach counts length first then removes node in second pass (O(2n)), this uses one pass with two pointers (O(n))

Edge Cases

Remove head node (n equals list length)

Dummy node allows removal without special case

DSA Javascript

const dummy = new ListNode(0, head); // dummy node before head

Single node list, remove 1st from end

Returns null as list becomes empty

DSA Javascript

slow.next = slow.next.next;

n is 1 (remove last node)

Slow pointer stops at second last node and removes last

DSA Javascript

while (fast.next !== null) { slow = slow.next; fast = fast.next; }

When to Use This Pattern

When asked to remove a node from the end of a linked list in one pass, use two pointers spaced n apart to find the target efficiently.

Common Mistakes

Mistake: Not using a dummy node and failing when removing the head node
Fix: Add a dummy node before head to simplify removal logic

Mistake: Moving fast pointer n times but not checking if fast is null (list shorter than n)
Fix: Ensure input n is valid or add checks before moving fast pointer

Mistake: Moving slow pointer too early or too late, missing the node before target
Fix: Keep fast pointer n steps ahead and move both until fast.next is null

Summary

Removes the Nth node from the end of a singly linked list in one pass.

Use when you need efficient single-pass removal from the end without counting length first.

Keep two pointers with a gap of N nodes so the slow pointer stops just before the node to remove.

Practice

1. What does the problem Remove Nth Node from End of List ask you to do?

easy

A. Delete the node that is the nth from the end in a linked list

B. Add a new node at the nth position from the start

C. Reverse the linked list up to the nth node

D. Find the value of the nth node from the start

Solution

1. Step 1: Understand the problem statement

   The problem asks to remove a node counting from the end of a linked list, not from the start.

2. Step 2: Identify the correct action

   Removing the nth node from the end means deleting that specific node and linking its previous node to the next node.

3. Final Answer:

   Delete the node that is the nth from the end in a linked list -> Option A

4. Quick Check:

   Remove nth from end = Delete nth from end [OK]

Hint: Count nodes from end, not start, to remove correct node [OK]

Common Mistakes:

• Confusing nth from end with nth from start
• Trying to reverse the list instead of removing
• Removing the wrong node index

2. Which of the following is the correct way to declare a function in JavaScript to remove the nth node from the end of a singly linked list?

easy

A. function removeNthFromEnd(head, n) { /* code */ }

B. removeNthFromEnd = (head, n) => { /* code */ }

C. All of the above

D. const removeNthFromEnd = function(head, n) { /* code */ }

Solution

1. Step 1: Review JavaScript function declaration styles

   JavaScript supports function declarations, function expressions, and arrow functions.

2. Step 2: Check each option

   function removeNthFromEnd(head, n) { /* code */ } is a function declaration, B is an arrow function, C is a function expression. All are valid ways to declare functions.

3. Final Answer:

   All of the above -> Option C

4. Quick Check:

   All function styles valid in JS [OK]

Hint: JS allows multiple function declaration styles [OK]

Common Mistakes:

• Thinking only one function syntax is valid
• Confusing arrow functions with older syntax
• Missing const or function keyword

3. What will be the output linked list after running this code snippet?

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

function removeNthFromEnd(head, n) {
  let dummy = new ListNode(0, head);
  let first = dummy;
  let second = dummy;
  for (let i = 0; i <= n; i++) {
    first = first.next;
  }
  while (first !== null) {
    first = first.next;
    second = second.next;
  }
  second.next = second.next.next;
  return dummy.next;
}

// List: 1 -> 2 -> 3 -> 4 -> 5 -> null
let head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
let newHead = removeNthFromEnd(head, 2);

// Print list
let result = [];
while (newHead) {
  result.push(newHead.val);
  newHead = newHead.next;
}
console.log(result);

medium

A. [1, 2, 3, 4]

B. [1, 2, 4, 5]

C. [2, 3, 4, 5]

D. [1, 2, 3, 5]

Solution

1. Step 1: Understand the code logic

   The code uses two pointers with a dummy node to remove the nth node from the end. Here, n=2 means remove the 2nd last node (value 4).

2. Step 2: Trace the linked list after removal

   Original list: 1 -> 2 -> 3 -> 4 -> 5. Removing node with value 4 results in 1 -> 2 -> 3 -> 5.

3. Final Answer:

   [1, 2, 3, 5] -> Option D

4. Quick Check:

   Remove 2nd last node = remove 4 [OK]

Hint: Use two pointers spaced n apart to find node to remove [OK]

Common Mistakes:

• Removing the wrong node counting from start
• Not using dummy node causing errors on head removal
• Off-by-one error in loop for pointer movement

4. Identify the bug in this code snippet for removing the nth node from the end of a linked list:

function removeNthFromEnd(head, n) {
  let dummy = new ListNode(0, head);
  let first = dummy;
  let second = dummy;
  for (let i = 0; i < n; i++) {
    first = first.next;
  }
  while (first.next !== null) {
    first = first.next;
    second = second.next;
  }
  second.next = second.next.next;
  return dummy.next;
}

medium

A. The while loop condition should be first !== null instead of first.next !== null

B. The for loop should run from i = 0 to i <= n to move first pointer correctly

C. The dummy node is not needed and causes errors

D. second.next = second.next.next should be second.next.next = second.next

Solution

1. Step 1: Analyze the for loop pointer movement

   The for loop moves the first pointer n times, which is correct to create a gap of n nodes between first and second pointers.

2. Step 2: Understand the while loop condition

   The while loop condition should be first !== null to ensure the first pointer reaches the end, allowing the second pointer to point to the node before the target.

3. Final Answer:

   The while loop condition should be first !== null instead of first.next !== null -> Option A

4. Quick Check:

   Use while (first !== null) to correctly position second pointer [OK]

Hint: Use while (first !== null) to move pointers correctly [OK]

Common Mistakes:

• Moving first pointer only n times instead of n+1
• Incorrect while loop condition causing null errors
• Removing dummy node mistakenly

5. Given a linked list 1 -> 2 -> 3 -> 4 -> 5 -> null, what will be the resulting list after removing the 5th node from the end using the standard two-pointer approach?

hard

A. [1, 2, 3, 4]

B. [2, 3, 4, 5]

C. [1, 3, 4, 5]

D. [1, 2, 3, 5]

Solution

1. Step 1: Identify the node to remove

   Removing the 5th node from the end means removing the first node (value 1) because the list length is 5.

2. Step 2: Remove the head node and link next node as new head

   After removal, the list starts from node with value 2: 2 -> 3 -> 4 -> 5.

3. Final Answer:

   [2, 3, 4, 5] -> Option B

4. Quick Check:

   Remove 5th from end = remove head [OK]

Hint: Removing nth from end where n = list length removes head [OK]

Common Mistakes:

• Not handling removal of head node correctly
• Returning original list without removal
• Confusing nth from end with nth from start