Merge two sorted singly linked lists into one sorted list by reusing the existing nodes.
Problem
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.
Goal
Produce a single sorted list by repeatedly choosing the smaller current node from the two lists until both lists are exhausted.
Input Format
- Two linked-list heads:
list1andlist2 - Each list is sorted in non-decreasing order
- Nodes contain integer values
Output Format
- Return the head of the merged sorted linked list
Constraints
- Both input lists may be empty
- The lists are singly linked
- Values are sorted in non-decreasing order
- Reuse existing nodes when possible
- Time complexity should be linear in the total number of nodes
Example 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
Unlock deeper context for this problem
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.