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:

Image for post
Image for post
Image for post
Image for post
Image for post
Image for post
(photo taken from Leetcode: https://leetcode.com/problems/merge-two-sorted-lists/)

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.

Image for post
Image for post

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:

Image for post
Image for post

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:

Image for post
Image for post

Repeat this process until L1 pointer or L2 pointer points to the null end, which means, one of the input linked list is depleted:

Image for post
Image for post

Since input linked lists are sorted, we can just connect cur.next to the rest of input linked list L1:

Image for post
Image for post

And the merging is done!

Python Code:

Image for post
Image for post

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!

Written by

Life is beautiful!

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store