Solving the LeetCode "Remove Nth Node From End of List" Problem in Go

Difficulty: Medium | Tags: Linked List, Two Pointers

Introduction

Removing the nth node from the end of a linked list is a common problem that tests understanding of linked list traversal and pointer manipulation. The challenge lies in efficiently finding the target node in a single pass.

Problem Analysis

Given a singly linked list, we need to remove the nth node from the end. For example, if the list is [1,2,3,4,5] and n=2, the result should be [1,2,3,5]. Edge cases include removing the only node (n=1) or the head node (n=sz).

Solution Approach

We use the two-pointer technique to solve this in one pass. A fast pointer moves n steps ahead first, then both fast and slow pointers move together until fast reaches the end. The slow pointer will then be at the node before the target, allowing us to skip the nth node.

Go Implementation

/**
* Definition for singly-linked list.
* type ListNode struct {
    *     Val int
    *     Next *ListNode
    * }
    */
    func removeNthFromEnd(head *ListNode, n int) *ListNode {
        dummy := &ListNode{Next: head}
        slow, fast := dummy, dummy
        // Move fast n steps ahead
        for i := 0; i <= n; i++ {
            fast = fast.Next
        }
        // Move both until fast reaches end
        for fast != nil {
            slow = slow.Next
            fast = fast.Next
        }
        // Skip the nth node
        slow.Next = slow.Next.Next
        return dummy.Next
    }

Complexity Analysis

Time Complexity: O(L), where L is the length of the linked list. We traverse the list once with the two pointers.
Space Complexity: O(1), as we only use constant extra space for the pointers.

Testing and Examples

Test cases should include:
1. Removing the last node (n=1)
2. Removing the head node (n=sz)
3. A middle node (n=2 in [1,2,3,4,5])
4. A single-node list (n=1)

Best Practices and Tips

1. Always use a dummy node to handle edge cases like removing the head.
2. Ensure the fast pointer moves n+1 steps initially to position the slow pointer correctly.
3. Verify the solution with lists of varying lengths and positions of n.