There are 2 single linked list, one is ascending sorted, the other is descending sorted, write code to merge them together, result in ascending sorted.
For example:
L1: 1->2->3
L2: 6->5->4
Result:
1->2->3->4->5->6
Requirements:
Time complexity: O(M + N), M is the length of L1, and N is the length of L2
Space complexity: O(1)
Please write code to solve the problem, please define data structure that need to be used to solve the problem.
The task is to merge one ascending singly linked list and one descending singly linked list into a single ascending list with O(M+N) time and O(1) extra space. A common approach is to first reverse the descending list in-place to make it ascending, then merge the two sorted lists node by node. It tests linked list manipulation and reasoning about time and space complexity.
The VOprep team has long accompanied candidates through various major company OAs and VOs, including Google, Amazon, Citadel, SIG, providing real-time voice assistance, remote practice, and interview pacing reminders to help you stay smooth during critical moments. If you are preparing for these companies, you can check out our customized support plans—from coding interviews to system design, we offer full guidance to help you succeed.
