Python Program to Merge Two Sorted Linked Lists

Overview

This Python program merges two sorted singly linked lists and returns a new linked list containing all elements from both lists, sorted in non-decreasing order. The merging is done iteratively by comparing the nodes from the two lists.

Program Explanation

The structure of the program includes a Node class to represent a node in a linked list and a function to merge two sorted linked lists.

Steps Involved:

1. Create a class Node to represent the elements of the linked list. Each node has two attributes: data (value of the node) and next (pointer to the next node).
2. Create a function merge_sorted_lists that takes two linked list heads and merges them by comparing nodes.
3. The new merged list will start with a dummy node and use a pointer to track the position in the merged list.
4. Compare the data of each node from both lists and append the smaller value to the new list. Continue until all nodes are processed.
5. After the merging loop, if any nodes are remaining in one of the lists, append them to the merged list.
6. Return the next of the dummy node, which is the head of the merged sorted list.

Python Code


class Node:
"""
Node class to represent a linked list node.
Each node contains the data and a pointer to the next node.
"""
def __init__(self, data):
self.data = data
self.next = None

def merge_sorted_lists(list1, list2):
“””
Merge two sorted linked lists into a single sorted linked list.

:param list1: Head node of the first sorted linked list
:param list2: Head node of the second sorted linked list
:return: Head node of the merged sorted linked list
“””
# Create a dummy node to act as the starting point for the merged list
dummy = Node(0)
current = dummy # Pointer to build the merged list

# Traverse both lists and merge them based on node values
while list1 is not None and list2 is not None:
if list1.data <= list2.data: current.next = list1 list1 = list1.next else: current.next = list2 list2 = list2.next current = current.next # If any elements remain in list1, append them if list1 is not None: current.next = list1 # If any elements remain in list2, append them elif list2 is not None: current.next = list2 # The merged list starts after the dummy node return dummy.next # Helper function to print a linked list def print_linked_list(head): “”” Print the elements of a linked list starting from the head node. :param head: Head node of the linked list “”” current = head while current is not None: print(current.data, end=” -> “)
current = current.next
print(“None”)

# Example usage:
# Create two sorted linked lists
a = Node(1)
a.next = Node(3)
a.next.next = Node(5)

b = Node(2)
b.next = Node(4)
b.next.next = Node(6)

# Merge the lists
merged_list = merge_sorted_lists(a, b)

# Print the merged list
print_linked_list(merged_list)

Program Explanation

This Python program defines the following:

• Node class: Each node in the linked list contains a value (data) and a reference to the next node (next).
• merge_sorted_lists function: Merges two sorted linked lists by iterating through both lists, comparing node values, and appending the smaller node to the new list. The remaining elements from either list are appended to the result at the end.
• print_linked_list function: A utility function to display the merged list for clarity.

Example Output

Given the two linked lists:

• List 1: 1 -> 3 -> 5 -> None
• List 2: 2 -> 4 -> 6 -> None

The merged list will be:

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> None