Merge Two Sorted Lists in Python

A linked list is a collection of nodes where each node contains a value and a pointer to the next node. It is used to store data in a sequence. In this blog, we will solve the problem of "merge two sorted linked lists" into a single sorted linked list. This is a common question in coding interviews and competitive programming.

The idea is simple. We will compare the values from both lists, pick the smaller value, and add it to a new list. We will repeat this process until we have processed all nodes in both lists. The final result will be a single sorted linked list.

Steps to Solve Merge Two Sorted Lists Problem

• Start with two sorted linked lists. These are the input lists.
• Create a dummy node. This helps in simplifying the process of creating the new list.
• Initialize pointers. Use two pointers to traverse both linked lists.
• Compare the values. Check the value of the current node in both lists. Add the smaller value to the new list.
• Move the pointer forward. Shift the pointer in the list from which the value was taken.
• Repeat the process. Continue until one or both lists are completely traversed.
• Attach the remaining nodes. If one list still has nodes, add all of them to the new list.
• Return the merged list. Skip the dummy node and return the new list starting from the next node.

Did you ever have this happen, where you were staring at two sorted lists, and then out of nowhere your brain says, "How do you merge these two?" It seems so trivial, right? But without the right method, it rapidly becomes a source of annoyance.

Let me narrate a story of Jane - a new developer - who had this very problem and discovered the ideal way of merging two sorted lists.

Jane's coding challenge

She was a brilliant young developer, exploding with enthusiasm to prove herself in her very first job. The manager gave her the task of merging two sorted lists into one. "This is going to be easy," she thought, but it turned out that the problem was a bit more complex than the requirements on the surface.

She tried all kinds but none could efficiently work. Till now, fed up with her work, Jane chose to go to her mentor, who bestowed on her some good tips. And today, I'm going to share those same tips with you.

Step 1: Know the basics

Before explore the solution, Jane's mentor explained the importance of understanding why merging two sorted lists is crucial. This task is fundamental in many areas, like data processing and search optimization, where time and resource efficiency are key.

Step 2: Pick the right tools

Jane learned that choosing the right data structures is crucial. Typically, arrays or linked lists are used. Her mentor explained the pros and cons:

• Arrays: Great for quick access.
• Linked Lists: Ideal for frequent insertions and deletions.

Step 3: Use a simple method

Her mentor introduced Jane to the two-pointer technique, a simple yet powerful method to merge two sorted lists. Here's the pseudo code he shared with her:

Pseudo code

• Initialize two pointers, i and j, to zero.
• Create an empty list merged_list.
• While both pointers are within the length of their respective lists:
  • Compare the elements at list1[i] and list2[j].
  • Append the smaller element to merged_list.
  • Move the pointer of the list from which the element was taken.
• If any elements remain in either list, append them to merged_list.
• Return merged_list.

Python code example

1def merge_two_sorted_lists(list1, list2):
2    merged_list = []
3    i, j = 0, 0
4
5    while i < len(list1) and j < len(list2):
6        if list1[i] < list2[j]:
7            merged_list.append(list1[i])
8            i += 1
9        else:
10            merged_list.append(list2[j])
11            j += 1
12
13    merged_list.extend(list1[i:])
14    merged_list.extend(list2[j:])
15    return merged_list

Step 4: Handle special cases

Jane's mentor advised her to ensure her code could handle edge cases, like empty lists or lists of different lengths. This made her solution robust and reliable.

Step 5: Improve performance

For larger datasets, Jane learned that performance optimization is key. Her mentor showed her how to use heaps to speed up the process:

1from heapq import merge
2
3def merge_two_sorted_lists_heap(list1, list2):
4    return list(merge(list1, list2))

Step 6: Test your code

Jane tested her code with various inputs to ensure it worked in all scenarios. This thorough testing helped her catch and fix any bugs.

Step 7: Real-world use

Merging sorted lists is useful in many real-world applications, like combining search results or datasets. Jane was thrilled to see how her solution could be applied in different contexts.

Conclusion

By following these steps, Jane mastered the art of merging two sorted lists. This skill not only helped her with her project but also made her a more efficient and confident developer.