NUHMAN.com

Introduction

LeetCode 21: Merge Two Sorted Lists is a classic linked list problem. Given two sorted singly linked lists, the task is to merge them into one sorted list.

This is a foundational problem that demonstrates how to traverse and manipulate linked lists efficiently in Go.

Problem Statement

You are given the heads of two sorted linked lists list1 and list2. Merge the two lists in a way that the resulting list is also sorted and return its head.

Examples

go

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
go

Input: list1 = [], list2 = []
Output: []
go

Input: list1 = [], list2 = [0]
Output: [0]

Approach: Iterative Merge with Dummy Node

1. Use a dummy node to simplify edge cases and hold the merged list.
2. Use a tail pointer to build the new list as you compare nodes from both lists.
3. Traverse both lists:

• Always attach the smaller node to tail.Next.
• Move the corresponding pointer forward.

1. Once one list ends, attach the rest of the other list to tail.Next.

Go Implementation

go

package main

import (
    "fmt"
)

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

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    dummy := &ListNode{}
    tail := dummy

    for list1 != nil && list2 != nil {
        if list1.Val < list2.Val {
            tail.Next = list1
            list1 = list1.Next
        } else {
            tail.Next = list2
            list2 = list2.Next
        }
        tail = tail.Next
    }

    if list1 != nil {
        tail.Next = list1
    } else {
        tail.Next = list2
    }

    return dummy.Next
}

Helper Functions for Testing

go

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

// Prints linked 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() {
    list1 := createList([]int{1, 2, 4})
    list2 := createList([]int{1, 3, 4})

    fmt.Print("List 1: ")
    printList(list1)
    fmt.Print("List 2: ")
    printList(list2)

    merged := mergeTwoLists(list1, list2)
    fmt.Print("Merged List: ")
    printList(merged)
}

Step-by-Step Example

Given:

ini

list1 = 1 → 2 → 4
list2 = 1 → 3 → 4

Merged process:

csharp

1 (from list1)
1 (from list2)
2 (from list1)
3 (from list2)
4 (from list1)
4 (from list2)

Result:

1 → 1 → 2 → 3 → 4 → 4

Time and Space Complexity

• Time Complexity: O(n + m), where n and m are the lengths of the two lists.
• Space Complexity: O(1), since we only use pointers and no extra data structures (excluding output list).

Key Takeaways

• This problem is a great example of using pointers to manipulate and merge linked structures.
• The dummy node pattern helps avoid special case handling for the head.
• You can also solve it recursively—great for interviews if you want to show alternate styles.