0021. Merge Two Sorted Lists
Easy | Linked List + Recursion | 16ms (98.84%), 13.4 MB (87.61%)
Source: LeetCode - Merge Two Sorted Lists GitHub: Solution / Performance
Merge two sorted linked lists and return them as a sorted list. The list should be made by "splicing" together (with) the nodes of the first two lists.
Constraints:
The number of nodes in both lists is in the range
[0, 50].-100 <= Node.val <= 100Both
l1andl2are sorted in non-decreasing order.
Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]
Input: l1 = [], l2 = []
Output: []
Input: l1 = [], l2 = [0]
Output: [0]Therefore, top-down recursion could help us sort by in-place modification on either l1 or l2 as a starting node.
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
# (base case)
if not l2 and l1: return l1
if not l1 and l2: return l2
if not l1 and not l2: return None
# ==================================================
# Linked List + Recursion =
# ==================================================
# n is the length of l1, and m is the length of l2
# time : O(n+m)
# space : O(n+m)
if l1.val > l2.val: l1, l2 = l2, l1
l1.next = self.mergeTwoLists(l1.next, l2)
return l1class Solution {
/**
* @time : O(n+m)
* @space : O(n+m)
*/
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
/* base case */
if(l1 != null && l2 == null) return l1;
if(l1 == null && l2 != null) return l2;
if(l1 == null && l2 == null) return null;
if(l2.val < l1.val) {
ListNode tmp = l1;
l1 = l2;
l2 = tmp;
}
l1.next = mergeTwoLists(l1.next, l2);
return l1;
}
}Last updated
Was this helpful?