Crack Leetcode 21: Merge Two Sorted Lists
There is a way to make it easy.
Sometimes they make it look hard, while in fact, there’s always a way you can easily understand. Today, we’ll crack leetcode 21 — Merge Two Sorted Lists — together. Without further ado, let’s get started.
Problem Description:
Solution:
Ideation:
An important information here is that both of the input linked lists are sorted in non-decreasing order. Therefore, we only need to focus on how to merge them correctly.
Let’s use this example to explain: Input L1=[1, 2, 4, 5], L2=[1, 3].
We use 1 Node called “res” as dummy head, and 3 Nodes as pointers. Their initial positions are shown as below.
The grey pointer is called “cur pointer”. It marks the current position, which you will understand later. The other two pointers are moving along L1 or L2, so I’ll just call them “L1 pointer”, “L2 pointer”.
Now we start Step #1: compare values pointed by L1, L2 pointers. 1==1, in this case I’ll just connect cur to the 1 in L1 (You can totally choose L2, no problem). So cur.next is 1 in L1, and then move the cur, L1 pointer forward for one step:
Now step#2: same process, compare values pointed by L1, L2 pointers. 1<2, so we cur.next is 1 in L2, and then move the cur, L2 pointers forward for one step:
Repeat this process until L1 pointer or L2 pointer points to the null end, which means, one of the input linked list is depleted:
Since input linked lists are sorted, we can just connect cur.next to the rest of input linked list L1:
And the merging is done!
Python Code:
Complexity Analysis:
Time Complexity:
(*Note: I tried my best. If there’s anything not correct, please let me know and I’ll check again. Thanks!)
- Worst-Case:
In the worst case, we have to go over both lists. Therefore, the worst-case time complexity is O(M+N), where M and N are the list length of input list L1 and L2.
- Best-Case:
In the best case, one array’s largest value is smaller than or equal to the smallest value in the other. Therefore, we need to go over only this input list. =>The best-case time complexity is O(min(M, N)).
- Average-Case:
In the average case, I sum up the expectation of each possible case, meaning, if in last step, there’s 1, or 2, or 3, …. or (M-1) elements left in L1, or if in last step , there’s 1, or 2, or 3, … or (N-1) elements left in L2.
The sum = 3/4 *(M+N)+1/2 - 1/2*[(M+1)/N + (N+1)/M].
When M, N both -> +oo, the average-case time complexity = O(M+N).
Space Complexity:
Since it used several nodes as pointers or dummy head, and when input lists increases in length, the auxiliary space consumption doesn’t change. Therefore, the (auxiliary) space complexity = O(1).
The END:
Thanks for reading! Please check our articles more often, if you’d like to support our work — and we’ll see you in the next one!
