Remove Nth Node from End of List in DSA Go

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 between them.

Analogy: Imagine two friends walking on a path where one starts n steps ahead. When the front friend reaches the end, the back friend is right before the target spot 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 2nd node from the end, which is node with value 4

Step 1: Move fast pointer n=2 steps ahead

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

Why: Create a gap of n between slow and fast pointers

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

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

Why: Keep the gap so slow points to node before target

Step 3: Slow pointer is before node to remove; skip next node

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

Why: Remove the 4 by linking 3 directly to 5

Result:

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

Annotated Code

DSA Go

package main

import "fmt"

type ListNode struct {
    Val  int
    Next *ListNode
}

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{0, head} // dummy node before head
    slow, fast := dummy, dummy

    // Move fast pointer n steps ahead
    for i := 0; i < n; i++ {
        fast = fast.Next
    }

    // Move both pointers until fast reaches the end
    for fast.Next != nil {
        slow = slow.Next
        fast = fast.Next
    }

    // Skip the nth node from end
    slow.Next = slow.Next.Next

    return dummy.Next
}

func printList(head *ListNode) {
    curr := head
    for curr != nil {
        fmt.Printf("%d", curr.Val)
        if curr.Next != nil {
            fmt.Printf(" -> ")
        }
        curr = curr.Next
    }
    fmt.Println(" -> null")
}

func main() {
    // Create list 1->2->3->4->5
    head := &ListNode{1, &ListNode{2, &ListNode{3, &ListNode{4, &ListNode{5, nil}}}}}

    n := 2
    fmt.Printf("Original list: ")
    printList(head)

    head = removeNthFromEnd(head, n)

    fmt.Printf("After removing %dth node from end: ", n)
    printList(head)
}

dummy := &ListNode{0, head} // dummy node before head

Create dummy node to handle edge cases like removing head

fast = fast.Next

Advance fast pointer n steps ahead to create gap

for fast.Next != nil { slow = slow.Next fast = fast.Next }

Move slow and fast together until fast reaches last node

slow.Next = slow.Next.Next

Remove nth node by skipping it in the list

Output

Original list: 1 -> 2 -> 3 -> 4 -> 5 -> null

After removing 2th node from end: 1 -> 2 -> 3 -> 5 -> null

Complexity Analysis

Time: O(n) because we traverse the list twice with two pointers but only once overall

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; this uses two pointers in one pass, saving time

Edge Cases

Removing head node (n equals list length)

Dummy node allows removal without special case

DSA Go

dummy := &ListNode{0, head} // dummy node before head

Single node list, remove 1st from end

Returns empty list (nil)

DSA Go

slow.Next = slow.Next.Next

n is 1 (remove last node)

Slow pointer stops at second last node and removes last

DSA Go

for fast.Next != nil { slow = slow.Next; fast = fast.Next }

When to Use This Pattern

When asked to remove the nth node from the end in a linked list, use two pointers with a gap of n to find the node before the target in one pass.

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 for nil, causing runtime errors
Fix: Ensure fast pointer is not nil before moving; input constraints usually guarantee valid n

Summary

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

Use when you need to delete a node counting from the list's end efficiently.

Keep two pointers n nodes apart so when the front reaches the end, the back is just before the target.

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