Remove Nth Node from End of List in DSA Javascript - Execution Trace

Concept Flow - Remove Nth Node from End of List

Create dummy node pointing to head

↓

Set two pointers: first and second at dummy

↓

Move first pointer n+1 steps ahead

↓

Move first and second pointers together until first reaches end

↓

Second pointer now at node before target

↓

Remove target node by changing second.next

↓

Return dummy.next as new head

We use two pointers spaced n+1 apart to find the node before the one to remove, then adjust links to remove it.

Execution Sample

DSA Javascript

function removeNthFromEnd(head, n) {
  let dummy = { val: 0, next: 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;
}

Removes the nth node from the end of a singly linked list using two pointers.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create dummy node pointing to head	0 -> 1 -> 2 -> 3 -> 4 -> 5 -> null	dummy -> 0, dummy.next -> 1	dummy(0) -> 1 -> 2 -> 3 -> 4 -> 5 -> null
2	Initialize first and second at dummy	0 -> 1 -> 2 -> 3 -> 4 -> 5 -> null	first = dummy(0), second = dummy(0)	first(0), second(0) -> 1 -> 2 -> 3 -> 4 -> 5 -> null
3	Move first pointer n+1=3 steps ahead	0 -> 1 -> 2 -> 3 -> 4 -> 5 -> null	first moves: 0->1, 1->2, 2->3	first(3), second(0) -> 1 -> 2 -> 3 -> 4 -> 5 -> null
4	Move first and second together until first reaches end	0 -> 1 -> 2 -> 3 -> 4 -> 5 -> null	first: 3->4, second: 0->1	first(4), second(1) -> 2 -> 3 -> 4 -> 5 -> null
5	Move first and second together	0 -> 1 -> 2 -> 3 -> 4 -> 5 -> null	first: 4->5, second: 1->2	first(5), second(2) -> 3 -> 4 -> 5 -> null
6	Move first and second together	0 -> 1 -> 2 -> 3 -> 4 -> 5 -> null	first: 5->null, second: 2->3	first(null), second(3) -> 4 -> 5 -> null
7	Remove node after second (node 4)	0 -> 1 -> 2 -> 3 -> 4 -> 5 -> null	second.next = second.next.next (4->5)	0 -> 1 -> 2 -> 3 -> 5 -> null
8	Return dummy.next as new head	1 -> 2 -> 3 -> 5 -> null	head = dummy.next (1)	1 -> 2 -> 3 -> 5 -> null
9	Exit	N/A	N/A	N/A

💡 first pointer reached null, removal done, list updated

Variable Tracker

Variable	Start	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	Final
dummy	node(0)->1	node(0)->1	node(0)->1	node(0)->1	node(0)->1	node(0)->1	node(0)->1
first	node(0)	node(3)	node(4)	node(5)	null	null	null
second	node(0)	node(0)	node(1)	node(2)	node(3)	node(3)	node(3)
head	node(1)	node(1)	node(1)	node(1)	node(1)	node(1)	node(1)

Key Moments - 3 Insights

Why do we create a dummy node before the head?

The dummy node helps handle cases where the head itself is removed. It simplifies pointer changes by always having a node before the target.

Why move the first pointer n+1 steps ahead instead of n?

Moving first pointer n+1 steps ahead ensures the second pointer stops exactly before the node to remove, allowing easy removal by changing second.next.

What happens if n equals the length of the list?

The dummy node allows removal of the head node safely because second will be at dummy, and second.next will be the head to remove.

Visual Quiz - 3 Questions

Look at the execution table at Step 3, where is the first pointer located?

A At node with value 2

B At node with value 3

C At dummy node

D At node with value 1

💡 Hint

Check the 'Pointer Changes' column in Step 3 of the execution table.

At which step does the second pointer move from node 1 to node 2?

A Step 5

B Step 6

C Step 4

D Step 3

💡 Hint

Look at the 'Pointer Changes' column for second pointer movements in the execution table.

If n was 1 (removing last node), what would be the pointer position of second before removal?

A At dummy node

B At last node

C At node before last node

D At head node

💡 Hint

Recall the two-pointer spacing and how second points to node before target before removal.

Concept Snapshot

Remove Nth Node from End of List:
- Use dummy node before head to simplify edge cases
- Set two pointers at dummy
- Move first pointer n+1 steps ahead
- Move both pointers until first reaches end
- Second pointer points to node before target
- Change second.next to skip target node
- Return dummy.next as new head

Full Transcript

This concept shows how to remove the nth node from the end of a singly linked list using two pointers. We start by creating a dummy node pointing to the head to handle edge cases like removing the head itself. Two pointers, first and second, start at the dummy. We move the first pointer n+1 steps ahead so that when it reaches the end, the second pointer is right before the node to remove. Then, we move both pointers together until the first pointer reaches the end of the list. At this point, the second pointer's next node is the target node to remove. We remove it by changing second.next to skip the target node. Finally, we return dummy.next as the new head of the list. This method ensures a single pass through the list and handles all cases cleanly.

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