LeetCode #21: Merge Two Sorted Lists
Introduction
Welcome fellow reader and aspiring leet coder. Today I’d like to walk you through a leet code problem that expanded my understanding of linked lists and how you can merge them. I’ll show you my initial thoughts, my attempt, high-light my misunderstanding, and provide a proper solution to this problem. By taking this very human approach, you’ll gain some insight and confidence in attacking those head-scratching problems.
The Prompt
The Prompt:Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.
Thoughts
It’s pretty straight forward and invokes a memory I had about being stuck in traffic with my father when I was a kid. Imagined merging into traffic with a police officer conducting traffic. The officer directed two lanes seemingly endless lanes of traffic. We call this a “bottle-neck” in the tri-state area. You see this in the entrances of tunnels and bridges during rush hour.
Let’s say our imaginary officer does this by numbering each car in each lane in ascending order. So it’s sort of like a queue. Each lane has ascending values like 1,3,5,6 values but always like 1,2,3,4… etc. Let’s leave the imagining here for now.
- Our output should be a merged linked list; let’s make a brand new one!
- Our input is two sorted linked lists; their values are sorted but not sequenced like 1,2,3,4,5…
- Conditional Logic: Lower values always are inserted first, so the position doesn’t matter
- How will I settle ties? Let’s make the default list be “l1”.
- We will need to update our references after each node gets inserted into our new list.
- We will use a loop to move through the linked lists.
- Sometimes a linked list can insert its nodes more than once since it could have the lowest value.
The Attempt
Sadly for this problem, it’s B.Y.O.C.(Bring.Your.Own.Class). You’ll have to do the work yourself here. Using a class and constructor method, created a linked list class outside of the function provided. I won’t get into the nuts and bolts, but you can see below in my example, it’s not too difficult. I also encourage you to play around with .next and .val on two input lists; you’ll need to understand what they actually return.
class List {
constructor(val = null, next = null) {
this.val = val <= number value of current node
this.next = next <= rest of values AFTER current node !
}
}Let’s start this list by declaring it; I added a value lower than what we would get in our lists. Make sure you save it to a variable as well. You will need it for reference later. I also saved the entire list as to a variable called the head. I will want to grab off of this later.
let mergeTwoLists = function(l1, l2) {let result = new List(-1)
let head = result}
Let’s figure out how we can move through these lists. Perhaps a while loop would be a good choice here. It can break on the event we hit the tail of either linked lists.
while(l1 !== null && l2 !== null) {
... Both lists shouldn't be null ...
};The Logic shouldn’t be too crazy here. We need to access the values of each current node in each list. After that will compare the two. Pick a winner and update the list with that winner. We should also update our new list so we don’t overwrite what we just added.
Note: use '<=' , it deals with any ties !!!if(l1.val <= l2.val) { ... }
result = result.next <= so we don't overwrite our added node !!!
Inside the if statement will add the entire linked list AFTER the first value of our new linked list. Weird right, but keep reading further to see how this plays out. We will also update our linked list with the lowest value (l1 or l2, depending on who wins!). After this, updates our linked list winner to a linked list without the current value that won.
if(l1.val <= l2.val) {. <= what's the lower value? Who wins ??? result.next = l1.next <= if winner, add whole list
l1 = l1.next <= update list without current value } else {
result.next = l2.next <= if winner, same deal
l2 = l2.next <= update the same way
...
At this point, I ran out of time. I shrugged and looked at what I had so far. It made sense, and I also tested out what I had. Surprisingly it all seemed to work so far. I wasn’t able to append the rest of the remaining list. Which was a bummer, but At least I was on the right track.
The Take-Away
Never enough time… oh well. Let’s see if I can finish this off the clock. Clearly, I needed a conditional statement to tie up the remaining linked list. It also occurred to me that the lengths of these lists could vary, so that needed to be accounted for as well. So let’s arrange ideas and build them out.
My Thoughts:
- Attach remaining list like so… result.next = l1 or l2
- Null is when the shorter or first list empties.
- We need to return the newly merged list.
if(l1 !== null) { <= If first list IS NOT null
result.next = l1 <= add rest of list to result
} else {
result.next = l2 <= add rest of list to result
}
return head.next <= We don't want the first value, just everything after it
};The Solution
const mergeTwoLists = function(l1, l2) {
let result = new List(-1)
let head = result
while(l1 !== null && l2 !== null) {
if(l1.val <= l2.val) {
result.next = l1
l1 = l1.next
} else {
result.next = l2
l2 = l2.next
}
result = result.next
};
if(l1 !== null) {
result.next = l1
} else {
result.next = l2
}
return head.next
};class List {
constructor(val = null, next = null) {
this.val = val
this.next = next
}
}
Conclusion
Sometimes, you’ll run out of time. What can I say? Rome wasn’t built in a day. More importantly, I learned I was on the right track, remembered my singly linked list data structure, and could build one on the fly! Not bad for a culinary major. Even if you didn’t get this far, don’t sweat it. It’s more important you fail every day with linked lists, then succeed and forget.
Personally, I time myself for 40 mins to see how I utilize time in a pressured situation. It’s a great consequence-free way to build up comfort in an interview environment. You also learn roughly how long it takes you to come up with a solid approach. For me, it’s about 5 -9 mins to think out a problem, writing the code is the rest of that time.
Not terrible, but I could improve here. More importantly, It’s a realistic view of where my time goes under pressure, and that’s important. Where you get stuck also becomes crystal clear during a timed session. Making it a faster process in identifying what I don’t know or need to work on.
I hope this has been an insightful approach to learning. I like taking the approach of narrating my thoughts to help others understand. It’s also fun to write about what you learn as well. If you liked this blog, don’t be afraid to hit the clap button below. Happy coding!
LeetCode:
Great Video Explanation: Terrible WhiteBoard https://www.youtube.com/watch?v=orCMI6WjoIw&t=4s
