NUHMAN.com

Introduction

LeetCode 19: Remove Nth Node From End of List is a popular problem that tests your understanding of linked lists and pointer manipulation. The challenge is to remove the nth node from the end of a singly linked list in one pass.

In this article, we’ll walk through a clean solution using the two-pointer (fast and slow) technique and implement it in Go (Golang).

Problem Statement

Given the head of a linked list, remove the nth node from the end of the list and return its head.

You must do this in one pass.

Examples

Example 1:

go

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Example 2:

go

Input: head = [1], n = 1
Output: []

Example 3:

go

Input: head = [1,2], n = 1
Output: [1]

Approach: Two Pointers (Fast and Slow)

1. Create a dummy node before the head to handle edge cases easily.
2. Move a fast pointer n+1 steps ahead of the slow pointer.
3. Move both pointers together until the fast pointer reaches the end.
4. Now, the slow pointer is just before the node to remove.
5. Adjust slow.Next to skip the target node.

Go Implementation

go

package main

import (
    "fmt"
)

// Definition for singly-linked list.
type ListNode struct {
    Val  int
    Next *ListNode
}

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

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

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

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

    return dummy.Next
}

// Helper function to create a linked list from slice
func createList(nums []int) *ListNode {
    dummy := &ListNode{}
    current := dummy
    for _, val := range nums {
        current.Next = &ListNode{Val: val}
        current = current.Next
    }
    return dummy.Next
}

// Helper to print list
func printList(head *ListNode) {
    for head != nil {
        fmt.Print(head.Val)
        if head.Next != nil {
            fmt.Print(" -> ")
        }
        head = head.Next
    }
    fmt.Println()
}

func main() {
    tests := []struct {
        nums []int
        n    int
    }{
        {[]int{1, 2, 3, 4, 5}, 2},
        {[]int{1}, 1},
        {[]int{1, 2}, 1},
    }

    for _, test := range tests {
        head := createList(test.nums)
        fmt.Print("Original List: ")
        printList(head)
        result := removeNthFromEnd(head, test.n)
        fmt.Printf("After removing %d-th node from end: ", test.n)
        printList(result)
        fmt.Println("---")
    }
}

Step-by-Step Example: [1, 2, 3, 4, 5], n = 2

• Create a dummy node → dummy → 1 → 2 → 3 → 4 → 5
• Fast pointer moves 3 steps ahead (n+1 = 3): now at node 3
• Move fast and slow together until fast reaches the end
• Slow is now at node 3 → skip node 4 by slow.Next = slow.Next.Next
• Final list: 1 → 2 → 3 → 5

Time and Space Complexity

• Time Complexity: O(L), where L is the length of the list (single pass)
• Space Complexity: O(1), no extra space used

Key Takeaways

• Use a dummy node to simplify head removal cases.
• Move fast pointer n+1 steps ahead to ensure the gap.
• Ideal demonstration of the two-pointer pattern in linked list problems.