Write a function that takes in the heads of two Singly Linked Lists that are in sorted order. The function should merge the lists in place (i.e., it shouldn't create a brand new list) and return the head of the merged list in sorted order.
Each LinkedList node has an integer value as well as a next, pointing to the next node in the list or to null if it's the tail of the list.
class ListNode {
constructor(value) {
this.value = value;
this.next = null;
}
}
headOne = 2 -> 6 -> 7 -> 8 // the head node with value 2
headTwo = 1 -> 3 -> 4 -> 5 -> 9 -> 10 // the head node with value 1
mergeLinkedLists(headOne, headTwo) = 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 // the new head node with value 1
Make sure the interviewee understands the structure of a LinkedList and its constraints - how to traverse a linked list, access its values and next nodes. Remember that they have to move the respective heads of the LL to its .next value after they merge the nodes in place.
Because the lists are already sorted, traditional sorting algorithms won't be needed.
The interviewee can implement this algorithm either iteratively or recursively since both follow nearly identical logic.
Interviewees should be able to get an approach by using a 2 pointers method. Make sure they remember to reconnect the pointer if they're merging 1 of the Linked Lists to the other so there aren't any misdirected or dangling pointers.
Alternatively, another approach can be to use a temporary head to keep track of its nodes - you will need to create a new linkedList node to keep track of your merged LL.
-
You can use pointers to keep track of which node you are at in each LL.
-
You can iterate through the Linked Lists from head to tail and merge them along the way by inserting nodes from the second Linked List into the first Linked List.
Solution 1: Iterative
function mergeLinkedLists(headOne, headTwo) {
let p1 = headOne;
let p1Prev = null;
let p2 = headTwo;
while (p1 !== null && p2 !== null) {
if (p1.value < p2.value) {
p1Prev = p1;
p1 = p1.next;
} else {
if (p1Prev !== null) p1Prev.next = p2;
p1Prev = p2;
p2 = p2.next;
p1Prev.next = p1;
}
}
if (p1 === null) p1Prev.next = p2;
return headOne.value < headTwo.value ? headOne : headTwo;
}Time Complexity - O(n+m), Space Complexity - O(1)
Solution 2: Recursive
function mergeLinkedLists(headOne, headTwo) {
recursiveMerge(headOne, headTwo, null);
return headOne.value < headTwo.value ? headOne : headTwo;
}
function recursiveMerge(p1, p2, p1Prev) {
if (p1 === null) {
p1Prev.next = p2;
return;
}
if (p2 === null) return;
if (p1.value < p2.value) {
recursiveMerge(p1.next, p2, p1);
} else {
if (p1Prev !== null) p1Prev.next = p2;
const newP2 = p2.next;
p2.next = p1;
recursiveMerge(p1, newP2, p2);
}
}Time Complexity - O(n+m), Space Complexity - O(n+m) where n = headOne.length and m = headTwo.length
I added a couple other approaches to solve this problem if you did not attempt it like the ones above. Rule #1 - draw out the Linked Lists so you can visualize where the node is pointing and where you want it to point to next. Walk through your code and change the pointers respectively so you can keep track of where they go and that you don't have any misdirected nodes or else your LL will be lost in the sauce.
Solution 1: Iterative
const mergeTwoLists = (l1, l2) => {
let merged = new ListNode();
let curr = merged;
while (l1 !== null && l2 !== null) {
//if l1's head.val is <= l2's head.val, you set that to your merged LL and reset head of l1.
if (l1.val <= l2.val) {
curr.next = l1;
l1 = l1.next;
} else {
//Same as above but flipped
curr.next =l2;
l2 = l2.next;
}
//set curr to next node as you continue traversing
curr = curr.next;
}
//since one of the LLs will have an extra node(s), you need to account for that and add it to curr.next
if (l1 === null) curr.next = l2
if (l2 === null) curr.next = l1
//return from merged.next since we started tracking it after setting up a temp head.
return merged.next;Time Complexity - O(n+m), Space Complexity - O(1)
Solution 2: Recursive
const mergeTwoLists = (l1, l2) => {
//base case
if (l1 === null) {
return l2;
} else if (l2 === null) {
return l1;
}
let head;
//set head to a new ListNode with the lowest val of the two LLs.
//Recursively call function with the with the selected LL to its next val.
if (l1.val <= l2.val) {
head = new ListNode(l1.val);
head.next = mergeTwoLists(l1.next, l2)
} else {
head = new ListNode(l2.val);
head.next = mergeTwoLists(l1, l2.next)
}
return head;
};Time Complexity - O(n+m), Space Complexity - O(n+m) *note that this does create a new LL