May 15, 2019

# Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

``````Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
``````

``````function ListNode(val) {
this.val = val;
this.next = null;
}
``````

### Solution

``````/**
* Merge Two Sorted Lists
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
* @time complexity: O(n + m)
*  where n and m are the size of l1 and l2 respectively
* @space complexity: O(1)
*  not allocating extra memory space instead reference to existing list node
*/
function mergeTwoLists(l1, l2) {
if (!l1) {
return l2;
}

if (!l2) {
return l1;
}

const dummy = new ListNode();
let curr = dummy;

while (l1 || l2) {
if (!l1 || (l2 && l2.val < l1.val)) {
curr.next = l2;
l2 = l2.next;
} else {
curr.next = l1;
l1 = l1.next;
}
curr = curr.next;
}

return dummy.next;
};
``````

### Test Case

``````function toList(arr) {
const dummy = new ListNode();
let curr = dummy;

for (let n of arr) {
curr.next = new ListNode(n);
curr = curr.next;
}

return dummy.next;
}

function toArray(list) {
const arr = [];

while (list) {
arr.push(list.val);
list = list.next;
}

return arr;
}

describe('Merge Two Sorted Lists', () => {
it('should return sorted list', () => {
const l1 = toList([1, 2, 4]);
const l2 = toList([1, 3, 4]);
const result = mergeTwoLists(l1, l2);
assert.deepEqual(toArray(result), [1, 1, 2, 3, 4, 4]);
});
it('should return l1 list when l2 is empty', () => {
const l1 = toList([1]);
const l2 = toList([]);
const result = mergeTwoLists(l1, l2);
assert.deepEqual(toArray(result), [1]);
});
it('should return l2 list when l1 is empty', () => {
const l1 = toList([]);
const l2 = toList([1]);
const result = mergeTwoLists(l1, l2);
assert.deepEqual(toArray(result), [1]);
});
it('should return empty list', () => {
const l1 = toList([]);
const l2 = toList([]);
const result = mergeTwoLists(l1, l2);
assert.deepEqual(toArray(result), []);
});
});
``````
``````  Merge Two Sorted Lists
✓ should return sorted list
✓ should return l1 list when l2 is empty
✓ should return l2 list when l1 is empty
✓ should return empty list

4 passing (14ms)
``````