Solving Remove Nth Node From End in Go: Step-by-Step Guide

Introduction to Remove Nth Node From End of List

The "Remove Nth Node From End of List" problem is a classic linked list challenge frequently encountered in coding interviews and algorithm practice. Given the head of a singly linked list and an integer n, the task is to remove the n-th node from the end of the list and return the updated head. While the problem sounds straightforward, it tests your understanding of pointer manipulation, edge cases, and algorithmic optimization.

In Go, where manual memory management is handled by the garbage collector but pointer operations remain explicit, this problem offers an excellent opportunity to sharpen your skills with structs, pointers, and idiomatic Go patterns. This tutorial walks you through everything you need to know, from understanding the problem to implementing an optimal one-pass solution.

Why This Problem Matters

Linked lists are foundational data structures that appear in many real-world systems, from memory allocators to blockchain implementations. The ability to traverse, modify, and reason about linked structures is essential for any serious developer. The "Remove Nth Node From End" problem specifically teaches several valuable lessons:

Pointer manipulation: You learn how to safely rewire node references without causing memory leaks or nil pointer dereferences.
Edge case handling: The problem forces you to consider scenarios like removing the head node, single-node lists, and removing the last node.
Algorithmic optimization: It demonstrates the power of the two-pointer technique, transforming a naive two-pass solution into an elegant one-pass algorithm.
Interview readiness: This problem appears frequently at companies like Amazon, Microsoft, and Google, making it a must-know for job seekers.

Understanding the Problem

Before writing any code, let's clearly define the problem. Consider a linked list: 1 -> 2 -> 3 -> 4 -> 5 and n = 2. The 2nd node from the end is node 4. After removal, the list becomes 1 -> 2 -> 3 -> 5.

Key observations to keep in mind:

The counting is 1-indexed from the end, meaning n = 1 refers to the last node.
The input guarantees that n is valid (between 1 and the length of the list).
You must return the head of the modified list, which may differ from the input head if the first node is removed.

Defining the Linked List Node in Go

In Go, we represent a singly linked list node using a struct with a value and a pointer to the next node:

package main

type ListNode struct {
    Val  int
    Next *ListNode
}

This simple struct is the building block for all operations. The Next field is a pointer, allowing us to chain nodes together and rewire connections as needed.

Approach 1: Two-Pass Solution

The most intuitive approach involves two passes through the list. First, calculate the total length of the list. Then, compute the position of the node to remove from the start, which is length - n. Traverse again to that position and adjust the pointers.

Implementation

func removeNthFromEndTwoPass(head *ListNode, n int) *ListNode {
    // First pass: calculate the length of the list
    length := 0
    current := head
    for current != nil {
        length++
        current = current.Next
    }

    // Calculate the position from the start (0-indexed)
    posFromStart := length - n

    // Edge case: removing the head node
    if posFromStart == 0 {
        return head.Next
    }

    // Second pass: traverse to the node just before the one to remove
    current = head
    for i := 0; i < posFromStart-1; i++ {
        current = current.Next
    }

    // Remove the target node by skipping it
    current.Next = current.Next.Next

    return head
}

Analysis of the Two-Pass Approach

This solution works correctly and is easy to understand. However, it traverses the list twice, resulting in a time complexity of O(L) where L is the length of the list. The space complexity is O(1) since we only use a few pointer variables. While acceptable, we can do better with a single traversal.

Approach 2: Two-Pointer One-Pass Solution

The optimal solution uses two pointers, often called "fast" and "slow." The idea is to maintain a gap of n nodes between them. When the fast pointer reaches the end, the slow pointer will be positioned just before the node to remove.

Using a Dummy Node for Edge Cases

A common pitfall is handling the case where the head node itself needs to be removed. To simplify this, we introduce a dummy node that points to the head. This way, every node (including the head) has a predecessor, and we can uniformly apply the removal logic.

Implementation

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    // Create a dummy node that points to the head
    dummy := &ListNode{Val: 0, Next: head}
    
    fast := dummy
    slow := dummy

    // Move fast pointer n+1 steps ahead so the gap between
    // fast and slow is exactly n nodes
    for i := 0; i <= n; i++ {
        fast = fast.Next
    }

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

    // slow.Next is the node to remove; skip it
    slow.Next = slow.Next.Next

    // Return the new head (dummy.Next handles head removal)
    return dummy.Next
}

How the Two-Pointer Technique Works

Let's trace through an example with the list 1 -> 2 -> 3 -> 4 -> 5 and n = 2:

Initialize dummy -> 1 -> 2 -> 3 -> 4 -> 5, with both fast and slow pointing to dummy.
Move fast forward n + 1 = 3 steps: fast now points to node 3.
Move both pointers until fast is nil. After the loop, slow points to node 3.
Set slow.Next = slow.Next.Next, which removes node 4.
Return dummy.Next, which is still node 1.

The result is 1 -> 2 -> 3 -> 5, exactly as expected.

Time and Space Complexity

The one-pass solution traverses the list exactly once, giving it a time complexity of O(L) where L is the list length. The space complexity remains O(1) since we only use a constant number of pointers. While the asymptotic complexity is the same as the two-pass approach, the one-pass solution is roughly twice as fast in practice because it halves the number of node traversals.

Testing the Solution

A robust solution requires thorough testing. Let's write a helper function to create a linked list from a slice and another to convert it back to a slice for easy verification.

package main

import "fmt"

type ListNode struct {
    Val  int
    Next *ListNode
}

func createList(values []int) *ListNode {
    if len(values) == 0 {
        return nil
    }
    head := &ListNode{Val: values[0]}
    current := head
    for i := 1; i < len(values); i++ {
        current.Next = &ListNode{Val: values[i]}
        current = current.Next
    }
    return head
}

func listToSlice(head *ListNode) []int {
    result := []int{}
    for head != nil {
        result = append(result, head.Val)
        head = head.Next
    }
    return result
}

func main() {
    // Test case 1: Remove 2nd from end
    list1 := createList([]int{1, 2, 3, 4, 5})
    result1 := removeNthFromEnd(list1, 2)
    fmt.Println(listToSlice(result1)) // Output: [1 2 3 5]

    // Test case 2: Remove the head (n equals list length)
    list2 := createList([]int{1, 2, 3})
    result2 := removeNthFromEnd(list2, 3)
    fmt.Println(listToSlice(result2)) // Output: [2 3]

    // Test case 3: Single node list
    list3 := createList([]int{1})
    result3 := removeNthFromEnd(list3, 1)
    fmt.Println(listToSlice(result3)) // Output: []

    // Test case 4: Remove the last node
    list4 := createList([]int{1, 2})
    result4 := removeNthFromEnd(list4, 1)
    fmt.Println(listToSlice(result4)) // Output: [1]
}

Running this program produces the expected output for all edge cases, confirming the correctness of the implementation.

Best Practices

Always Use a Dummy Node

The dummy node pattern is invaluable when working with linked lists. It eliminates special-case handling for head removal and makes your code cleaner and less error-prone. Without it, you would need additional conditional logic to check whether the node being removed is the head, which clutters the code and increases the chance of bugs.

Validate Input Assumptions

While the problem guarantees valid input, in production code you should always validate assumptions. Consider adding checks for nil heads, invalid n values, and empty lists. Defensive programming prevents panics and makes your code more robust:

func removeNthFromEndSafe(head *ListNode, n int) *ListNode {
    if head == nil || n <= 0 {
        return head
    }

    dummy := &ListNode{Val: 0, Next: head}
    fast := dummy
    slow := dummy

    // Move fast n+1 steps, with bounds checking
    for i := 0; i <= n && fast != nil; i++ {
        fast = fast.Next
    }

    // If n is larger than the list length, return original
    if fast == nil && n > 0 {
        // Check if we moved exactly n+1 steps
        // If not, n exceeds list length
    }

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

    if slow.Next != nil {
        slow.Next = slow.Next.Next
    }

    return dummy.Next
}

Leverage Go's Garbage Collection

In languages like C or C++, you would need to explicitly free the removed node to avoid memory leaks. In Go, the garbage collector automatically reclaims memory when no references to a node remain. However, be mindful of lingering references. If you store node pointers elsewhere, the garbage collector cannot reclaim that memory. Simply reassigning slow.Next = slow.Next.Next is sufficient because the removed node becomes unreachable.

Write Table-Driven Tests

Go's testing framework excels at table-driven tests. This pattern keeps your test cases organized and makes it easy to add new scenarios:

package main

import "testing"

func TestRemoveNthFromEnd(t *testing.T) {
    tests := []struct {
        name     string
        input    []int
        n        int
        expected []int
    }{
        {"remove middle", []int{1, 2, 3, 4, 5}, 2, []int{1, 2, 3, 5}},
        {"remove head", []int{1, 2, 3}, 3, []int{2, 3}},
        {"remove tail", []int{1, 2, 3}, 1, []int{1, 2}},
        {"single node", []int{1}, 1, []int{}},
        {"two nodes remove first", []int{1, 2}, 2, []int{2}},
        {"two nodes remove last", []int{1, 2}, 1, []int{1}},
    }

    for _, tt := range tests {
        t.Run(tt.name, func(t *testing.T) {
            list := createList(tt.input)
            result := removeNthFromEnd(list, tt.n)
            got := listToSlice(result)
            if len(got) != len(tt.expected) {
                t.Errorf("got %v, want %v", got, tt.expected)
                return
            }
            for i := range got {
                if got[i] != tt.expected[i] {
                    t.Errorf("got %v, want %v", got, tt.expected)
                    return
                }
            }
        })
    }
}

Avoid Common Pitfalls

Several mistakes commonly arise when solving this problem. First, forgetting the dummy node leads to nil pointer dereferences when removing the head. Second, miscounting the gap between the two pointers results in removing the wrong node. The gap must be exactly n + 1 steps so that slow lands on the node before the target. Third, not handling the single-node list case can cause unexpected behavior. Always test with minimal inputs to catch these issues early.

Conclusion

Solving the "Remove Nth Node From End of List" problem in Go is an excellent exercise in pointer manipulation, edge case handling, and algorithmic optimization. By starting with the intuitive two-pass approach and refining it into an elegant one-pass two-pointer solution, you gain a deeper understanding of how to reason about linked structures. The dummy node pattern, while simple, proves to be a powerful tool that simplifies head-removal edge cases and leads to cleaner code. Combined with Go's straightforward struct and pointer syntax, this problem demonstrates how the language's design encourages writing clear, efficient, and maintainable code. Whether you are preparing for interviews or building production systems, mastering these techniques will serve you well across a wide range of linked list challenges.