Merge Two Sorted Linked Lists

You are given two sorted linked lists and need to merge them into a single sorted linked list. This is a fundamental operation in many sorting algorithms and data structure manipulations, requiring efficient handling of ordered data.

Problem Description

Your task is to merge two sorted linked lists, list1 and list2, into one sorted linked list. The new linked list should contain all the nodes from the original two lists, also in non-decreasing order. You should do this by splicing together the nodes of the first two lists.

Key Requirements:

• The merged list must maintain the sorted order of elements from both input lists.
• You should create a new linked list by re-linking existing nodes, not by creating entirely new nodes for each element.
• The function should handle cases where one or both input lists are empty.

Expected Behavior:

The function should return the head of the newly merged sorted linked list.

Edge Cases:

• One or both input lists are empty.
• One list is significantly shorter than the other.
• Lists contain duplicate values.

Examples

Example 1:

Input:
list1: 1 -> 2 -> 4
list2: 1 -> 3 -> 4

Output:
1 -> 1 -> 2 -> 3 -> 4 -> 4

Explanation:
The nodes are merged in non-decreasing order.

Example 2:

Input:
list1: (empty)
list2: 0

Output:
0

Explanation:
When one list is empty, the other list is returned.

Example 3:

Input:
list1: 5
list2: 1 -> 2 -> 3 -> 4

Output:
1 -> 2 -> 3 -> 4 -> 5

Explanation:
The shorter list is placed at the beginning.

Constraints

• The number of nodes in both lists can range from 0 to 50.
• Node values will be integers between -100 and 100.
• Both list1 and list2 are sorted in non-decreasing order.
• The solution should aim for a time complexity of O(n + m), where n and m are the lengths of list1 and list2 respectively.

Notes

You can approach this problem using an iterative or recursive method. Consider how you will keep track of the current node in each list and how you will build the new merged list. A dummy head node can be very helpful in simplifying the logic for building the new list.