50. Merge Two Sorted Lists
Merge both lists so that all original nodes appear in nondecreasing value order. Build the merged chain by reconnecting the supplied nodes rather than copying their values into new nodes.
Preserve the relative order from each individual input. When values tie, the contract gives nodes from the first input priority.
Example 1
Input
A: A0(1) → A1(3); B: B0(2) → B1(4)
Output
A0 → B0 → A1 → B1 → null
Explanation: The returned reference is A0. Choosing A0 then B0 rewrites A0.next from A1 to B0; no value is copied.
Example 2
Input
A: A0(2) → A1(2); B: B0(2)
Output
A0 → A1 → B0 → null
Explanation: The <= comparison selects A on every tie, preserving the declared cross-input stability.
Example 3
Input
A: null; B: B0(7) → B1(9)
Output
B0 → B1 → null
Explanation: Attach B as a suffix and return the original B0. No input link needs changing.
Constraints
0 <= nodes per input list <= 105-231 <= node.value <= 231 - 1- Each input list is sorted in nondecreasing order.
Hints
Hint 1
The smaller of the two current heads must be the next output node. What tie rule is promised?
Hint 2
A dummy predecessor lets the first node use exactly the same linking operation as later nodes.
Hint 3
Link the selected head, advance that source, advance tail, then attach the nonempty suffix.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Interleaved identities and equal-value ties
[1,3,3]
[2,3,4]
["A0","B0","A1","A2","B1","B2"]