Remove Nth Node from End of List in DSA Go - Build from Scratch

Remove Nth Node from End of List

📖 Scenario: You are working on a simple contact list app. The contacts are stored in a singly linked list, where each node holds a contact's name. Sometimes, you need to remove a contact counting from the end of the list, for example, to delete the last contacted person or the second last.

🎯 Goal: Build a Go program that creates a singly linked list of contacts, then removes the nth node from the end of the list, and finally prints the updated list.

📋 What You'll Learn

Create a singly linked list with exactly these contacts in order: "Alice", "Bob", "Charlie", "Diana", "Eve"

Create an integer variable called n and set it to 2

Write a function called removeNthFromEnd that takes the head of the list and n, and removes the nth node from the end

Print the updated list using the format: Alice -> Bob -> Charlie -> Eve -> null

💡 Why This Matters

🌍 Real World

Linked lists are used in many applications like contact lists, music playlists, and undo history where elements are added or removed dynamically.

💼 Career

Understanding linked list operations is essential for software engineers, especially for roles involving system design, memory management, and algorithm optimization.

1

Create the linked list of contacts

Create a singly linked list with nodes containing these exact contact names in order: "Alice", "Bob", "Charlie", "Diana", "Eve". Use the struct ListNode with fields Val string and Next *ListNode. Create a variable called head pointing to the first node.

DSA Go

package main

import "fmt"

type ListNode struct {
    Val  string
    Next *ListNode
}

func main() {
    // Create linked list with nodes: "Alice", "Bob", "Charlie", "Diana", "Eve"
    // Your code here
}

Hint

Start by creating the first node with Val: "Alice". Then link each next node by setting the Next field.

2

Set the position to remove from the end

Create an integer variable called n and set it to 2 inside the main function.

DSA Go

package main

import "fmt"

type ListNode struct {
    Val  string
    Next *ListNode
}

func main() {
    head := &ListNode{Val: "Alice"}
    head.Next = &ListNode{Val: "Bob"}
    head.Next.Next = &ListNode{Val: "Charlie"}
    head.Next.Next.Next = &ListNode{Val: "Diana"}
    head.Next.Next.Next.Next = &ListNode{Val: "Eve"}

    // Create variable n and set it to 2
    // Your code here
}

Hint

Just write n := 2 inside the main function.

3

Write the function to remove the nth node from the end

Write a function called removeNthFromEnd that takes two parameters: head *ListNode and n int. It returns *ListNode. Use two pointers fast and slow starting at a dummy node before head. Move fast n+1 steps ahead, then move both pointers until fast reaches the end. Remove the node after slow by changing slow.Next. Return the new head from dummy.Next. Call this function in main with head and n, and update head with the result.

DSA Go

package main

import "fmt"

type ListNode struct {
    Val  string
    Next *ListNode
}

func main() {
    head := &ListNode{Val: "Alice"}
    head.Next = &ListNode{Val: "Bob"}
    head.Next.Next = &ListNode{Val: "Charlie"}
    head.Next.Next.Next = &ListNode{Val: "Diana"}
    head.Next.Next.Next.Next = &ListNode{Val: "Eve"}

    n := 2

    // Write and call removeNthFromEnd function
    // Your code here
}

Hint

Use a dummy node to handle edge cases. Move fast pointer n+1 steps ahead, then move both pointers until fast is nil. Remove the node after slow.

4

Print the updated linked list

Write a for loop to traverse the linked list starting from head. Print each node's Val followed by " -> ". After the loop, print "null" to show the end of the list.

DSA Go

package main

import "fmt"

type ListNode struct {
    Val  string
    Next *ListNode
}

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{Next: head}
    fast := dummy
    slow := dummy

    for i := 0; i <= n; i++ {
        fast = fast.Next
    }

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

    slow.Next = slow.Next.Next
    return dummy.Next
}

func main() {
    head := &ListNode{Val: "Alice"}
    head.Next = &ListNode{Val: "Bob"}
    head.Next.Next = &ListNode{Val: "Charlie"}
    head.Next.Next.Next = &ListNode{Val: "Diana"}
    head.Next.Next.Next.Next = &ListNode{Val: "Eve"}

    n := 2

    head = removeNthFromEnd(head, n)

    // Print the updated list
    // Your code here
}

Hint

Use a for loop to go through each node. Print the value and an arrow. After the loop, print "null".

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