21. Merge Two Sorted Lists

Today, I solved the Merge Two Sorted Lists. 

Description:

https://leetcode.com/problems/merge-two-sorted-lists/description/

We have two lists, and we are gonna merge those two lists. The point is that we are gonna sort new list in non-decreasing order.

Solution1:

Iteractive Solution

We make dummy node to avoid some error. And, we make curr node to know our location in both lists. 

Our while loop runs until we put every values in list1 and list2.

 

If the value of list1 is less than list2, then curr points to list1.next

else the value of list2 is less than list1, then curr points to list2.next

And then we move the curr to the location of curr.next

 

Now, our node looks like this:

[output] --> [dummy] --> [first value] --> [second value] ...

 

However, if list1 and list2 have different length, there should be remaining node in list1 or list2.

Before returning our output, we should make sure put every node to our output list.

 

Solution(Recursion Method):

Recursion Method

The algorithms is similar to the iteractive method. 

To avoid remaining elements in both lists, we put if not list1 or not list2: return list1 or list2 

 

Now, if the value of list1 is less than list2, we move to the next value of list1 with recursion method.

Otherwise, we move to the next value of list2.