21. Merge Two Sorted Lists
Solution#
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} list1
* @param {ListNode} list2
* @return {ListNode}
*/
var mergeTwoLists = function(list1, list2) {
// Edge case
if (!list1) return list2;
if (!list2) return list1;
let f = list1;
let s = list2;
let root = new ListNode();
const result = root;
while (f && s) {
if (f.val < s.val) {
root.next = f;
f = f.next;
} else {
root.next = s;
s = s.next;
}
root = root.next;
}
// After loop only one element remains.
if (f) {
root.next = f;
}
if (s) {
root.next = s;
}
return result.next;
};
Complexity#
- Time Complexity: O(N*M), where N and M are the size of the two lists.
- Space Complexity: O(1), we are not using extra memory, just shifting pointers.
All Solutions