Skip to main content

🟩 Merge Two Sorted Lists (#21)

🔗 Problem Link​

📋 Problem Statement​

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

💡 Examples​

Example 1​

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

Example 2​

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

Example 3​

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

🔑 Key Insights & Approach​

Core Observation: Use a dummy node to simplify edge cases. Compare nodes from both lists and append smaller one.

Why Dummy Node?

  • Eliminates special handling for head
  • Simplifies code
  • O(n + m) time, O(1) space

Approaches:

  1. Iterative with dummy node: O(n + m) time, O(1) space - optimal
  2. Recursive: O(n + m) time, O(n + m) space

Pattern: "Two Pointer Merge" pattern for sorted lists.

🐍 Solution: Python​

Approach 1: Iterative with Dummy Node​

Time Complexity: O(n + m) | Space Complexity: O(1)

from typing import Optional

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        # Create dummy node
        dummy = ListNode(0)
        current = dummy

        # Merge lists
        while list1 and list2:
            if list1.val <= list2.val:
                current.next = list1
                list1 = list1.next
            else:
                current.next = list2
                list2 = list2.next
            current = current.next

        # Attach remaining nodes
        current.next = list1 if list1 else list2

        return dummy.next

Approach 2: Recursive​

Time Complexity: O(n + m) | Space Complexity: O(n + m)

from typing import Optional

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if not list1:
            return list2
        if not list2:
            return list1

        if list1.val <= list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list1, list2.next)
            return list2

🔵 Solution: Golang​

Approach: Iterative​

Time Complexity: O(n + m) | Space Complexity: O(1)

type ListNode struct {
    Val  int
    Next *ListNode
}

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

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

    // Attach remaining
    if list1 != nil {
        current.Next = list1
    } else {
        current.Next = list2
    }

    return dummy.Next
}

📚 References​