Remove Nth Node from End of List in DSA Go - 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 Go

func removeNthFromEnd(head *ListNode, n int) *ListNode {
  dummy := &ListNode{Next: head}
  first, second := dummy, dummy
  for i := 0; i <= n; i++ {
    first = first.Next
  }
  for first != nil {
    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	dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null	dummy points to 1, first = dummy, second = dummy	dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
2	Move first pointer n+1=3 steps ahead	dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null	first moves: dummy->1->2->3	dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null first at 3, second at dummy
3	Move first and second pointers together until first reaches end	dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null	first: 3->4->5->null, second: dummy->1->2->3	dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null first at null, second at 3
4	Remove target node (second.Next = second.Next.Next)	dummy -> 1 -> 2 -> 3 -> 5 -> null	second.Next changed from 4 to 5	dummy -> 1 -> 2 -> 3 -> 5 -> null
5	Return dummy.Next as new head	1 -> 2 -> 3 -> 5 -> null	head updated to dummy.Next	1 -> 2 -> 3 -> 5 -> null
6	Exit	Operation complete	No more changes	Final list: 1 -> 2 -> 3 -> 5 -> null

💡 first pointer reached end, target node removed, list updated

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
dummy	points to head (1)	same	same	same	same
first	dummy	at node 3	at null	at null	at null
second	dummy	dummy	at node 3	at node 3	at node 3
head	1	1	1	1	1 (updated to dummy.Next)
List Nodes	1->2->3->4->5->null	same	same	4 removed: 1->2->3->5->null	1->2->3->5->null

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 just before the node to remove, as shown in execution_table step 2 and 3.

What happens if the node to remove is the head of the list?

Using a dummy node allows removal of the head node safely by adjusting dummy.Next, as seen in the final return step 5.

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

Dummy node simplifies edge cases like removing the first node, preventing null pointer errors, demonstrated in step 1 and final return.

Visual Quiz - 3 Questions

Look at the execution_table, at which step does the first pointer reach the end of the list?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Check the 'Pointer Changes' column in step 3 where first moves to null.

According to variable_tracker, what is the state of the list nodes after step 4?

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

B 2 -> 3 -> 4 -> 5 -> null

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

D 1 -> 3 -> 4 -> 5 -> null

💡 Hint

Look at the 'List Nodes' row under 'After Step 4' in variable_tracker.

If we remove the 1st node from the end (n=1), how would the pointer movement in step 2 change?

A first moves 2 steps ahead

B first moves 1 step ahead

C first moves 3 steps ahead

D first does not move

💡 Hint

Recall first pointer moves n+1 steps ahead; for n=1, that is 2 steps (see step 2).

Concept Snapshot

Remove Nth Node from End of List:
- Use dummy node before 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. We create a dummy node pointing to the head to handle edge cases. 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 just before the node to remove. Then we skip the target node by changing second.Next. Finally, we return dummy.Next as the new head of the list. The execution table traces each step, showing pointer movements and list changes. The variable tracker records pointer positions and list state after each step. Key moments clarify why we use n+1 steps, the dummy node, and how head removal works. The visual quiz tests understanding of pointer positions and list state changes during execution.

Practice

1. What does the problem "Remove Nth Node from End of List" ask you to do with a linked list?

easy

A. Reverse the linked list

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

C. Remove the node that is the Nth from the end of the list

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

Solution

1. Step 1: Understand the problem statement

   The problem requires removing the node that is Nth from the end, not from the start or adding nodes.

2. Step 2: Clarify the operation on the linked list

   We must delete the node counting from the end, which is different from reversing or finding a value.

3. Final Answer:

   Remove the node that is the Nth from the end of the list -> Option C

4. Quick Check:

   Remove Nth from end = Remove Nth node from end [OK]

Hint: Focus on 'Nth from end' means counting backwards [OK]

Common Mistakes:

• Confusing Nth from end with Nth from start
• Thinking the problem asks to add nodes
• Assuming the list should be reversed

2. Which of the following Go code snippets correctly declares a singly linked list node struct for this problem?

easy

A. type ListNode struct { Val int; Next *ListNode }

B. type ListNode struct { Value int; NextNode *ListNode }

C. struct ListNode { int Val; ListNode* Next; }

D. class ListNode { int Val; ListNode Next; }

Solution

1. Step 1: Identify Go struct syntax

   In Go, structs use 'type Name struct { fields }' and pointers use '*Type'.

2. Step 2: Match correct field names and types

   type ListNode struct { Val int; Next *ListNode } uses 'Val int' and 'Next *ListNode' which is the standard for singly linked list nodes in Go.

3. Final Answer:

   type ListNode struct { Val int; Next *ListNode } -> Option A

4. Quick Check:

   Go struct with pointer field = type ListNode struct { Val int; Next *ListNode } [OK]

Hint: Go structs use 'type' and pointers with '*' [OK]

Common Mistakes:

• Using C/C++ or Java syntax in Go code
• Missing pointer '*' for Next field
• Incorrect field names or types

3. What will be the linked list after removing the 2nd node from the end in this list: 1 -> 2 -> 3 -> 4 -> 5 -> null?

medium

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

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

C. 1 -> 2 -> 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 (1st), 4 (2nd). So node with value 4 is to be removed.

2. Step 2: Remove node with value 4 and link previous node to next

   Node 3's next should point to node 5, skipping node 4.

3. Final Answer:

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

4. Quick Check:

   Remove 2nd from end (4) = 1->2->3->5 [OK]

Hint: Count nodes from end to find which to remove [OK]

Common Mistakes:

• Removing the wrong node counting from start
• Breaking links incorrectly causing list corruption
• Off-by-one errors in counting nodes

4. Given this Go function snippet to remove the Nth node from end, what is the bug?

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{0, head}
    first, second := dummy, dummy
    for i := 0; i < n; i++ {
        first = first.Next
    }
    for first.Next != nil {
        first = first.Next
        second = second.Next
    }
    second.Next = second.Next.Next
    return head
}

medium

A. Missing check for empty list before loops

B. The loop runs n times instead of n+1 times

C. second pointer is not initialized correctly

D. Returns head instead of dummy.Next, so removal of first node fails

Solution

1. Step 1: Understand dummy node usage

   Dummy node helps handle edge cases like removing the first node. The result list starts at dummy.Next.

2. Step 2: Check return statement

   Returning 'head' ignores changes if first node was removed. Should return dummy.Next instead.

3. Final Answer:

   Returns head instead of dummy.Next, so removal of first node fails -> Option D

4. Quick Check:

   Return dummy.Next to handle first node removal [OK]

Hint: Always return dummy.Next after removal [OK]

Common Mistakes:

• Returning original head ignoring dummy node
• Not using dummy node for edge cases
• Incorrect loop bounds causing panic

5. You have a linked list: 10 -> 20 -> 30 -> 40 -> 50 -> null. You want to remove the 5th node from the end. What will be the resulting list?

hard

A. 20 -> 30 -> 40 -> 50 -> null

B. 10 -> 20 -> 30 -> 40 -> null

C. 10 -> 20 -> 30 -> 40 -> 50 -> null

D. 30 -> 40 -> 50 -> null

Solution

1. Step 1: Identify the 5th node from the end

   The list length is 5, so the 5th from end is the first node with value 10.

2. Step 2: Remove the first node and link dummy to second node

   Removing node 10 means the new head is node 20, so list becomes 20 -> 30 -> 40 -> 50 -> null.

3. Final Answer:

   20 -> 30 -> 40 -> 50 -> null -> Option A

4. Quick Check:

   Remove 5th from end (first node) = 20->30->40->50 [OK]

Hint: Nth from end equals list length means remove head [OK]

Common Mistakes:

• Removing wrong node when N equals list length
• Not updating head pointer after removal
• Confusing node positions counting from start vs end