# 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!