Merge two sorted singly linked lists into one sorted list by reusing the existing nodes.
You are given the heads of two singly linked lists, each sorted in non-decreasing order. Merge them into one sorted linked list that is also sorted in non-decreasing order.
You should return the head of the merged list. The merged list must be formed by connecting the original nodes; creating new nodes is usually unnecessary unless the interface requires it.
Produce a single sorted list by repeatedly choosing the smaller current node from the two lists until both lists are exhausted.
list1 and list2Example 1
Input
list1 = 1 -> 2 -> 4 list2 = 1 -> 3 -> 4
Output
1 -> 1 -> 2 -> 3 -> 4 -> 4
Explanation
Compare the heads step by step and always attach the smaller available node to the result.
Example 2
Input
list1 = list2 = 0
Output
0
Explanation
If one list is empty, the merged result is just the other list.
Premium problem context
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.