298. Merge Two Sorted Lists

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.

This is the fundamental merge operation used in merge sort and is a building block for merging K sorted lists.

Requirements

1. Basic Functionality

• Merge two sorted linked lists into one sorted list
• Handle empty lists
• Maintain sorted order

Example Usage

// list1: 1 → 2 → 4
// list2: 1 → 3 → 4
// merged: 1 → 1 → 2 → 3 → 4 → 4

Real-World Context

• Merge sort: Core operation in the merge sort algorithm
• Database merging: Combining sorted query results from different shards
• Log aggregation: Merging sorted log entries from multiple servers