Merge Two Sorted Lists In Descending Order
01 · Problem
You are given the heads of two singly linked lists list1 and list2, each sorted in non-decreasing order. Merge them into a single list sorted in non-increasing (descending) order and return its head.
Build the result by relinking the existing nodes in a single merge pass; do not merge in ascending order first and then reverse the whole list. Either input may be empty; if both are empty, return an empty list. Duplicate values are kept (every input node appears exactly once in the output).
02 · Examples
list1 = [1,3,5], list2 = [2,4,6]
[6,5,4,3,2,1]
All six nodes are merged and arranged from largest to smallest.
list1 = [1,1,4], list2 = [2,3]
[4,3,2,1,1]
Both copies of 1 are kept; the result is in descending order.
list1 = [], list2 = [0,7]
[7,0]
With list1 empty, the result is just list2 in descending order.
03 · Constraints
- 01The number of nodes in each list is in the range [0, 104].
- 02-105 <= Node.val <= 105
- 03Both list1 and list2 are sorted in non-decreasing order.
04 · Optimal complexity
- Time
- O(n + m)
- Space
- O(1)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.