700073. Merge 2 sorted linked list in reverse order
Merge 2 sorted linked list in reverse order
Slug: merge-2-sorted-linked-list-in-reverse-order
Difficulty: Medium
Id: 700073
Topic Tags: Linked List, Merge Sort, Data Structures, Algorithms
Company Tags: Microsoft
Summary
This problem requires us to merge two sorted linked lists in reverse order. We need to combine the nodes of both lists while maintaining their original sorting and then reverse the resulting list.
Detailed Explanation
To solve this problem, we can start by iterating over the second list (the one that should be merged last) and adding each node to a new list. Then, we iterate over the first list, adding nodes from it to our new list until we reach the end of the first list. Finally, we reverse the resulting list.
Here's a step-by-step breakdown:
- Create an empty list
resultthat will store the merged nodes. - Initialize two pointers,
p1andp2, to point to the beginning of each list. - While both lists have nodes:
- If the current node in the first list is less than or equal to the current node in the second list, add it to the result list and move
p1. - Otherwise, add the current node from the second list to the result list and move
p2.
- If the current node in the first list is less than or equal to the current node in the second list, add it to the result list and move
- Once one of the lists has been fully traversed, append the remaining nodes (if any) from the other list to the result.
- Reverse the result list.
The time complexity of this solution is O(n + m), where n and m are the lengths of the two input lists, since we're iterating over each node once. The space complexity is O(n + m) as well, since we're storing all nodes in the result list.
Optimized Solutions
Java
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode current = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
current.next = (l1 != null) ? l1 : l2;
return dummy.next;
}