# 21. Merge Two Sorted Lists — LeetCode(Python)

I got you!

# Problem:

You are given the heads of two sorted linked lists `list1`

and `list2`

.

Merge the two lists in a one **sorted** list. The list should be made by splicing together the nodes of the first two lists.

Return *the head of the merged linked list*.

**Example 1:**

**Input:** list1 = [1,2,4], list2 = [1,3,4]

**Output:** [1,1,2,3,4,4]

**Example 2:**

**Input:** list1 = [], list2 = []

**Output:** []

**Example 3:**

**Input:** list1 = [], list2 = [0]

**Output:** [0]

**Constraints:**

- The number of nodes in both lists is in the range
`[0, 50]`

. `-100 <= Node.val <= 100`

- Both
`list1`

and`list2`

are sorted in**non-decreasing**order.

# Solution:

## 1. Iterative Method —

`dummy = curr = ListNode()`

while list1 and list2:

if list1.val < list2.val:

curr.next = list1

list1 = list1.next

else:

curr.next = list2

list2 = list2.next

curr = curr.next

curr.next = list1 or list2

return dummy.next

## Explanation —

We start by creating a ** dummy** node that will come in handy while returning the merged list.

Now, we simply traverse both the lists until either one or both are exhausted.

If the current value of the ** list1** node is smaller than the value of the current

**node, we append the**

*list2***node to our**

*list1***’s**

*curr***pointer, and move to the**

*next***node in**

*next*

*list1.*Similarly, we append the ** list2** node to our

**’s**

*curr***pointer, and move to the**

*next***node in**

*next***if the value in**

*list2,***is smaller.**

*list2*After this, we also move the ** curr** node to it’s

**node.**

*next*The *while* loop **CAN** terminate if both the lists are exhausted. But what if the two lists were not of equal length?

We then point the ** next** pointer of our

**node to the remaining list, because we know that it is already sorted.**

*curr*Finally, we return the next node to our ** dummy** node which is where our new merged list starts from.

## Time and Space Complexity —

Since we are traversing through the lists only once, we can say that our code requires linear amount of time to run.

Also, we are using a constant amount of extra space.

Thus, if *m* is the length of ** list1** and

*n*is the length of

*list2,*Time Complexity: O(m+n)

Space Complexity: O(1)

## 2. Recursive Method —

`if not list1 or not list2:`

return list1 or list2

if list1.val < list2.val:

list1.next = self.mergeTwoLists(list1.next, list2)

return list1

else:

list2.next = self.mergeTwoLists(list1, list2.next)

return list2

## Explanation —

The termination condition of our recursion is when either of the lists has been exhausted; in which case, we return the remaining list.

If the value of the current node in ** list1** is smaller than that of

**, we call the function recursively on the remainder of**

*list2***and the entire**

*list1***— and we append this answer to our current**

*list2***node.**

*list1*Otherwise, we call the function recursively on ** list1** and the remainder of

**— and we append this answer to our current**

*list2***node.**

*list2*In both cases, we return the node containing the smaller number.

## Time and Space Complexity —

Since we are traversing through the lists only once, we can say that our code requires linear amount of time to run.

Also, since the recursion stack stores all elements in both the lists at some point, we need a linear amount of extra space.

Thus, if *m* is the length of ** list1** and

*n*is the length of

*list2,*Time Complexity: O(m+n)

Space Complexity: O(m+n)