Merge Two Sorted Lists: A Python Guide

Nov 15, 2025 by Alex Johnson 39 views

Let's dive into a classic problem in computer science: merging two sorted lists. This is a fundamental concept with applications in various algorithms and data structures. In this article, we'll explore a Python solution to efficiently merge two sorted linked lists into a single sorted list. We'll break down the code step by step, explaining the logic behind each decision and highlighting the key concepts involved.

Understanding the Problem

Before we jump into the code, let's clarify the problem. We are given two sorted linked lists, list1 and list2. Our goal is to create a new linked list that contains all the nodes from both input lists, sorted in ascending order. The original lists should remain unchanged. The new list is constructed by linking the nodes of the original lists in the correct order.

The Python Solution

Here's a Python solution to merge two sorted lists:

class Solution(object):
    def mergeTwoLists(self, list1, list2):
        # Create a dummy node to simplify edge cases
        dummy = ListNode(0)
        current = dummy

        # Traverse both lists and append the smaller node to the merged list
        while list1 and list2:
            if list1.val <= list2.val:
                current.next = list1
                list1 = list1.next
            else:
                current.next = list2
                list2 = list2.next
            current = current.next

        # Append the remaining nodes if any list is not empty
        current.next = list1 if list1 else list2

        # Return the merged list starting from the node after dummy
        return dummy.next

Step-by-Step Explanation

Dummy Node: We start by creating a dummy node. The dummy node simplifies the code, especially when dealing with the head of the merged list. It acts as a placeholder, allowing us to easily handle edge cases such as when one or both of the input lists are empty. We initialize a current pointer to the dummy node. This pointer will be used to traverse the merged list and append new nodes.
Traversing Both Lists: The core of the algorithm is a while loop that iterates as long as both list1 and list2 have nodes. Inside the loop, we compare the values of the current nodes in both lists. If the value of the current node in list1 is less than or equal to the value of the current node in list2, we append the node from list1 to the merged list. Otherwise, we append the node from list2. After appending the node, we advance the current pointer to the newly added node and move the pointer of the list from which the node was taken to the next node.
Appending Remaining Nodes: After the while loop finishes, one of the lists might still have remaining nodes. We need to append these remaining nodes to the merged list. We use a conditional expression to check if list1 or list2 is not empty. If list1 is not empty, we append the remaining nodes of list1 to the merged list. Otherwise, we append the remaining nodes of list2. This ensures that all nodes from both input lists are included in the merged list.
Returning the Merged List: Finally, we return the merged list starting from the node after the dummy node. The dummy node was just a placeholder, so we don't want to include it in the final result.

Code Deep Dive

Let's take a closer look at each part of the code.

Dummy Node Initialization

dummy = ListNode(0)
current = dummy

We create a ListNode with a value of 0. The value doesn't really matter, as this node is just a placeholder. The current pointer is initialized to the dummy node. This pointer will be used to build the merged list.

Traversing and Comparing Nodes

while list1 and list2:
    if list1.val <= list2.val:
        current.next = list1
        list1 = list1.next
    else:
        current.next = list2
        list2 = list2.next
    current = current.next

This while loop is the heart of the algorithm. It continues as long as both list1 and list2 have nodes. Inside the loop, we compare the values of the current nodes in both lists. If the value of the current node in list1 is less than or equal to the value of the current node in list2, we append the node from list1 to the merged list. Otherwise, we append the node from list2. After appending the node, we advance the current pointer to the newly added node and move the pointer of the list from which the node was taken to the next node.

Appending Remaining Nodes

current.next = list1 if list1 else list2

After the while loop finishes, one of the lists might still have remaining nodes. This line appends those remaining nodes to the merged list. It uses a conditional expression to check if list1 is not empty. If it's not, it appends the remaining nodes of list1 to the merged list. Otherwise, it appends the remaining nodes of list2.

Returning the Merged List

return dummy.next

Finally, we return the merged list, starting from the node after the dummy node. The dummy node was just a placeholder, so we don't want to include it in the final result.

Why This Solution Works

The algorithm works because it maintains the sorted order of the merged list at each step. By comparing the values of the current nodes in both lists and appending the smaller node to the merged list, we ensure that the merged list is always sorted. The use of a dummy node simplifies the code and makes it easier to handle edge cases.

Complexity Analysis

The time complexity of this algorithm is O(n + m), where n and m are the lengths of the two input lists. This is because we traverse both lists once. The space complexity is O(1), as we are not using any extra space that scales with the input size. We are only using a few constant space variables.

Alternative Approaches

While the above solution is efficient and commonly used, there are alternative approaches to merging two sorted lists. One alternative is to use recursion. However, the recursive approach might be less efficient due to the overhead of function calls. Another alternative is to convert the linked lists to arrays, merge the arrays, and then convert the merged array back to a linked list. However, this approach requires extra space to store the arrays.

Practical Applications

Merging sorted lists is a fundamental operation with applications in various areas of computer science. It's used in sorting algorithms, such as merge sort. It's also used in database systems for merging sorted data from multiple tables. Additionally, it can be used in data compression algorithms for merging sorted frequency lists.

Conclusion

In this article, we've explored a Python solution to merge two sorted lists. We've broken down the code step by step, explaining the logic behind each decision and highlighting the key concepts involved. We've also discussed the time and space complexity of the algorithm, alternative approaches, and practical applications. Mastering this fundamental concept will undoubtedly be beneficial in your journey as a software developer.

For more information on linked lists and merging algorithms, you can check out resources like Wikipedia's article on Merge Algorithms.