Merge Two Sorted Linked Lists

Problem

You are given the heads of two sorted (in ascending order) singly linked lists, list1 and list2. Your task is to merge these two lists into a single sorted linked list and return the head of the merged list.

The merged list should be constructed by splicing together the nodes of the two input lists (i.e., you should not create new nodes — reuse the existing ones).

Input / Output Format

Input:

• list1: head of the first sorted linked list
• list2: head of the second sorted linked list

Lists are represented as space-separated integers for input/output purposes.

Output:
The head of the merged sorted linked list, printed as space-separated integers.

Examples

Example 1

Input: list1 = [1, 2, 4], list2 = [1, 3, 5]
Output: [1, 1, 2, 3, 4, 5]
Explanation: Comparing nodes one by one:

• 1 (L1) vs 1 (L2) → take L2's 1, then L1's 1
• 2 (L1) vs 3 (L2) → take 2
• 4 (L1) vs 3 (L2) → take 3
• 4 (L1) vs 5 (L2) → take 4, then 5

Example 2

Input: list1 = [], list2 = [0]
Output: [0]
Explanation: list1 is empty, so the result is just list2.

Example 3

Input: list1 = [5], list2 = [1, 3, 7]
Output: [1, 3, 5, 7]
Explanation: 5 is inserted between 3 and 7 in list2.

Approach Hints

• Iterative approach: Use a dummy head node and a pointer current. At each step, compare the values at the heads of both lists, attach the smaller node to current, and advance that list's pointer. When one list is exhausted, attach the remainder of the other list. Time: O(m + n), Space: O(1).

• Recursive approach: Base cases handle empty lists. Recursively determine which node should come first by comparing values and linking the result of the recursive call to the chosen node. Time: O(m + n), Space: O(m + n) call stack.

• Think carefully about pointer manipulation to avoid losing references to nodes.