Remove Nth Node from End of List in DSA Typescript - 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 before target node

↓

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 target, then remove the target node by skipping it.

Execution Sample

DSA Typescript

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

This code 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	1 -> 2 -> 3 -> 4 -> 5 -> null	dummy -> dummyNode, dummy.next = head	dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
2	Set first and second pointers at dummy	1 -> 2 -> 3 -> 4 -> 5 -> null	first = dummy, second = dummy	dummy(first, second) -> 1 -> 2 -> 3 -> 4 -> 5 -> null
3	Move first pointer n+1=3 steps ahead	1 -> 2 -> 3 -> 4 -> 5 -> null	first moves: dummy->1->2->3	dummy -> 1 -> 2 -> 3(first) -> 4 -> 5 -> null
4	Move first and second pointers together until first reaches end	1 -> 2 -> 3 -> 4 -> 5 -> null	first: 3->4, second: dummy->1	dummy -> 1(second) -> 2 -> 3 -> 4(first) -> 5 -> null
5	Continue moving pointers	1 -> 2 -> 3 -> 4 -> 5 -> null	first: 4->5, second: 1->2	dummy -> 1 -> 2(second) -> 3 -> 4 -> 5(first) -> null
6	Continue moving pointers	1 -> 2 -> 3 -> 4 -> 5 -> null	first: 5->null, second: 2->3	dummy -> 1 -> 2 -> 3(second) -> 4 -> 5 -> null
7	Loop ends as first reaches null	1 -> 2 -> 3 -> 4 -> 5 -> null	first: null (no move), second at 3rd node	dummy -> 1 -> 2 -> 3(second) -> 4 -> 5 -> null
8	Remove target node (second.next = second.next.next)	1 -> 2 -> 3 -> 5 -> null	second.next changes from 4 to 5	dummy -> 1 -> 2 -> 3 -> 5 -> null
9	Return dummy.next as new head	1 -> 2 -> 3 -> 5 -> null	head = dummy.next	1 -> 2 -> 3 -> 5 -> null
10	End	1 -> 2 -> 3 -> 5 -> null	No pointer changes	Final list: 1 -> 2 -> 3 -> 5 -> null

💡 first pointer reached null, second pointer is before target node, removal done

Variable Tracker

Variable	Start	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	Final
dummy	dummyNode -> 1	dummyNode -> 1	dummyNode -> 1	dummyNode -> 1	dummyNode -> 1	dummyNode -> 1	dummyNode -> 1	dummyNode -> 1
first	dummyNode	3rd node (value 3)	4th node (value 4)	5th node (value 5)	null	null	null	null
second	dummyNode	dummyNode	1st node (value 1)	2nd node (value 2)	3rd node (value 3)	3rd node (value 3)	3rd node (value 3)	3rd node (value 3)
head	1st node (value 1)	1st node (value 1)	1st node (value 1)	1st node (value 1)	1st node (value 1)	1st node (value 1)	1st node (value 1)	1st node (value 1)

Key Moments - 3 Insights

Why do we 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, as shown in execution_table step 3 and 7.

What happens if the list has only one node and n=1?

The dummy node helps handle this edge case by allowing removal of the head node safely, as dummy.next will be updated to null.

Why do we use a dummy node instead of starting pointers at head?

Dummy node simplifies removal of head node and avoids null pointer errors, as seen in step 1 and throughout pointer movements.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, where is the first pointer located?

A At the 1st node with value 1

B At the 3rd node with value 3

C At the dummy node

D At the 2nd node with value 2

💡 Hint

Check the Pointer Changes and Visual State columns at step 3 in execution_table.

At which step does the second pointer move to the node before the target node to remove?

A Step 6

B Step 4

C Step 3

D Step 8

💡 Hint

Look at the Pointer Changes column to see when second pointer is before the node to remove.

If n was 1 (remove last node), how would the final list change compared to the current execution?

A The first node (1) would be removed

B The third node (3) would be removed

C The last node (5) would be removed

D No nodes would be removed

💡 Hint

Removing nth node from end with n=1 means removing the last node; check the logic in execution_table steps.

Concept Snapshot

Remove Nth Node from End of List:
- Use dummy node pointing to head
- Set two pointers at dummy
- Move first pointer n+1 steps ahead
- Move both pointers until first reaches end
- Second pointer is before target node
- Remove target by second.next = second.next.next
- 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 and a dummy node. First, a dummy node is created pointing to the head to handle edge cases. Two pointers, first and second, start at the dummy. The first pointer moves n+1 steps ahead to create a gap. Then both pointers move together until the first pointer reaches the end. At this point, the second pointer is just before the node to remove. The node is removed by changing second.next to skip the target node. Finally, dummy.next is returned as the new head of the list. The execution table traces each step, showing pointer positions and list state changes. Key moments clarify why n+1 steps are moved and why the dummy node is used. The visual quiz tests understanding of pointer positions and effects of changing n.

Practice

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

easy

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

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

C. Reverse the linked list up to the nth node

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

Solution

1. Step 1: Understand the problem statement

   The problem requires removing the node that is nth from the end of a singly linked list.

2. Step 2: Clarify the task

   We do not add or reverse nodes; we specifically remove the nth node counting from the list's end.

3. Final Answer:

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

4. Quick Check:

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

Hint: Focus on 'from end' meaning count backwards [OK]

Common Mistakes:

• Confusing nth from end with nth from start
• Thinking the problem is about reversing the list
• Assuming insertion instead of deletion

2. Which of the following TypeScript function signatures correctly represents a function to remove the nth node from the end of a singly linked list?

easy

A. function removeNthFromEnd(head: ListNode, n: string): ListNode

B. function removeNthFromEnd(head: number[], n: number): number[]

C. function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null

D. function removeNthFromEnd(n: number, head: ListNode): ListNode

Solution

1. Step 1: Check parameter types and order

   The function should take the head of a linked list (ListNode or null) and a number n, returning the possibly updated head.

2. Step 2: Validate correct types and order

   function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null matches this: head is ListNode|null, n is number, return type is ListNode|null.

3. Final Answer:

   function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null -> Option C

4. Quick Check:

   Correct signature uses ListNode and number types [OK]

Hint: Head first, then n; use ListNode type [OK]

Common Mistakes:

• Swapping parameter order
• Using array type instead of ListNode
• Using wrong type for n (string instead of number)

3. What is the output linked list after removing the 2nd node from the end in the list 1 -> 2 -> 3 -> 4 -> 5 -> null?

medium

A. 1 -> 2 -> 4 -> 5 -> null

B. 1 -> 2 -> 3 -> 5 -> null

C. 1 -> 3 -> 4 -> 5 -> null

D. 2 -> 3 -> 4 -> 5 -> null

Solution

1. Step 1: Identify the 2nd node from the end

   Counting from the end: 5 is 1st, 4 is 2nd node from the end.

2. Step 2: Remove the 4th node

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

3. Final Answer:

   1 -> 2 -> 3 -> 5 -> null -> Option B

4. Quick Check:

   2nd from end is 4, removed list matches 1 -> 2 -> 3 -> 5 -> null [OK]

Hint: Count from end, remove that node [OK]

Common Mistakes:

• Removing wrong node counting from start
• Removing node 3 instead of 4
• Confusing 2nd from end with 2nd from start

4. Given this TypeScript code snippet to remove the nth node from end, what is the bug?

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  let fast = head;
  let slow = head;
  for (let i = 0; i < n; i++) {
    fast = fast.next;
  }
  while (fast.next !== null) {
    fast = fast.next;
    slow = slow.next;
  }
  slow.next = slow.next.next;
  return head;
}

medium

A. It does not handle the case when n equals the length of the list

B. The loop runs one time too many causing runtime error

C. The slow pointer moves too fast and skips nodes

D. It returns the wrong head node

Solution

1. Step 1: Analyze fast pointer movement

   Fast pointer moves n steps ahead. If n equals list length, fast becomes null.

2. Step 2: Check while loop condition

   Code uses fast.next, but if fast is null, accessing fast.next causes error or skips removing head.

3. Step 3: Identify missing edge case handling

   Code does not handle removing the first node when n equals list length.

4. Final Answer:

   It does not handle the case when n equals the length of the list -> Option A

5. Quick Check:

   Edge case n = list length missing [OK]

Hint: Check if fast pointer is null after initial moves [OK]

Common Mistakes:

• Ignoring edge case when removing head node
• Assuming fast.next always exists
• Not returning updated head when head is removed

5. You have a linked list 1 -> 2 -> 3 -> 4 -> 5 -> null. You remove the 5th node from the end twice in a row. What is the final linked list?

hard

A. 2 -> 3 -> 4 -> 5 -> null

B. 3 -> 4 -> 5 -> null

C. 3 -> 4 -> null

D. 4 -> 5 -> null

Solution

1. Step 1: First removal of 5th node from end

   List length 5, 5th from end is head (1). After removal: 2 -> 3 -> 4 -> 5 -> null.

2. Step 2: Second removal of 5th node from end

   New length 4, n=5 > 4 so no 5th node exists; list unchanged: 2 -> 3 -> 4 -> 5 -> null.

3. Final Answer:

   2 -> 3 -> 4 -> 5 -> null -> Option A

4. Quick Check:

   Removing 5th from end twice removes head once [OK]

Hint: Removing nth from end twice may remove head once only [OK]

Common Mistakes:

• Confusing nth from end with nth from start
• Thinking the problem is about reversing the list
• Assuming insertion instead of deletion