Merge two sorted linked lists and return it as a new sorted 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 Definition for singly-linked list. function ListNode(val) { this.val = val; this.next = null; }
var mergeTwoLists = function(l1, l2) {
let cur1=l1;
let cur2=l2;
let result=new ListNode();
const head=result;
while (cur1 && cur2) {
if(cur2.val>=cur1.val) {
result.next=new ListNode(cur1.val);
cur1=cur1.next;
console.log("hit 1");
}
else {
result.next=new ListNode(cur2.val);
cur2=cur2.next;
console.log("hit 2");
}
result=result.next;
}
//add on remaining
if (cur1) {
result.next=cur1;
}
if (cur2) {
result.next=cur2;
}
return head.next;
};
Approach:
We loop through while both linked lists still have nodes. Since our operations within this loop depend on both lists, it would not be good if we ran out of either one. We’ll handle the case where one list is longer than the other at the end.
At each iteration, we take the node with the smaller number and attach it to our result. We then move forward on the list we just used (so we don’t use that same node again) and our result list (so it’s ready for the next node).
Then we deal with the case of one list being longer than the other list. We do that simply by attaching the list which still has elements to our result list.
Why do we not need a loop here? Well, the remaining nodes of either linked list are already connected, so we’re simply attaching the next node (with all of its linked nodes) to our resulting list. Think of a train of cars, when you attach another train of cars to the end of it, you don’t need to attach each car of that second train. You just attach the head and the rest of the train is connected.