Merging Harmony: Combining Two Sorted Linked Lists in Python

Introduction

Greetings, coding enthusiasts! Today, we’ll explore the art of merging two sorted linked lists. Understanding how to merge linked lists is a valuable skill that can be applied in various scenarios, especially when dealing with sorted data. In this blog post, we’ll dive into the intricacies of merging two sorted linked lists, demystify the process, and provide clear Python code examples.

The Symphony of Merging Sorted Linked Lists

Merging two sorted linked lists involves combining elements from both lists while maintaining the sorted order. This operation is fundamental in various algorithms and is a common task when dealing with sorted data structures.

Node Structure Recap

Before we dive into the merging process, let’s revisit the structure of a node in a linked list:

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next_node = None

Merging Two Sorted Linked Lists

The key to merging two sorted linked lists lies in comparing the values of the nodes and arranging them in ascending order. We’ll create a new linked list to hold the merged result.

def merge_sorted_lists(list1, list2):
    merged_head = Node()  # Dummy node to simplify the code
    current_node = merged_head

    while list1 and list2:
        if list1.data < list2.data:
            current_node.next_node = list1
            list1 = list1.next_node
        else:
            current_node.next_node = list2
            list2 = list2.next_node

        current_node = current_node.next_node

    # If one of the lists is longer, append the remaining nodes
    current_node.next_node = list1 or list2

    return merged_head.next_node

Let’s visualize this with an example:

# Creating two sorted linked lists: 1 -> 3 -> 5 and 2 -> 4 -> 6
list1 = Node(1)
list1.next_node = Node(3)
list1.next_node.next_node = Node(5)

list2 = Node(2)
list2.next_node = Node(4)
list2.next_node.next_node = Node(6)

# Merging the sorted linked lists: 1 -> 2 -> 3 -> 4 -> 5 -> 6
merged_list = merge_sorted_lists(list1, list2)