Merge Linked List Problem

Introduce

Continuing the Linked List topic in the Algorithm & Data Structure series, today I will introduce to you the Merge Linked List problem. In this article, I will give 2 ways to solve the problem and analyze the space and time complexity. I will assume that you already know about the linked list data structure when reading this article. If not, you can read the document "Basic linked list" of Stanford University, USA here.

Topic

Write a function that takes in 2 heads of two sorted Singly linked lists. Write a function that merges the two linked lists and returns the head of the merged sorted linked list.

Input:

Output:

In the next section, I will give two ways to solve this problem.

Solution 1: use list as intermediary

Similar to the previous linked list problems, we can solve this problem through lists and then reconstruct a linked list. Here is my description:

 

The detailed steps are as follows:

1. First we convert two linked lists into two lists
2. Then we merge those two lists together.
3. Newly created sort list
4. Construct new linked list based on sorted list

My solution to this approach:

Space and time complexity analysis:

Note: m and n are the lengths of the two linked lists respectively.

Space complexity is O(n + m)

The space complexity to listify two linked lists is O(n + m). The space complexity to construct a linked list from the new list is O(n + m). Therefore, the total space complexity is O(n + m).

Time complexity is O((n+m)log(n+m))

Time complexity to listify two linked lists is O(n+m) Time complexity to sort the list is O((n + m)log(n + m)) Time complexity to construct the linked list from the new list is O(n+m) Therefore, total time complexity is O((n + m)log(n + m)

Solution 2: Merge in place

Instead of going through the list like the above method, this way we will merge two linked lists right on the selected one. Here is my description:

 

The detailed steps are as follows:

1. Choose the head with the smaller value as the center - where the remaining linked list nodes will be inserted
2. Use two pointers if to insert nodes into the central linked list in order.
3. Loop through all nodes in both linked lists

My solution is as follows:

Space and time complexity analysis:

Note: m and n are the lengths of the two linked lists respectively.

Space complexity is O(1)

1. Since the entire algorithm is merged in place, the space complexity constant - O(1)

Time complexity is O(n+m)

1. The time complexity to iterate through each element of two linked lists is O(n + m)

III. Conclusion

The above two solutions are not all the ways to merge two linked lists, but they are two quite typical ways for this classic problem. Hopefully this blog post can help you in some way. If you find the blog post interesting, please share it so that more people know about it. And look forward to more of my blog posts on the topic of Data Structure & Algorithm on TipsMake's tech blog!