Python is an efficient, readable, powerful, high-level language with automatic memory management. With Python, we can merge two linked lists in a very efficient way (as shown below).
Remember, in
Python
we do not have any built-in linked list.
Let’s understand the algorithm for merging two sorted linked list with the illustration below:
In the code below, we have implemented a linked list in Python as well as the merge()
function.
# A single node of a singly linked listclass Node:# constructordef __init__(self, data = None, next=None):self.data = dataself.next = next# A Linked List class with a single head nodeclass LinkedList:def __init__(self):self.head = None# insertion method for the linked listdef insert(self, data):newNode = Node(data)if(self.head):current = self.headwhile(current.next):current = current.nextcurrent.next = newNodeelse:self.head = newNode# print method for the linked listdef printLL(self):current = self.headwhile(current):print(current.data)current = current.next#-----------------------Merge function---------------------#def merge(List_1, List_2):# Node for output LinkedListhead_ptr = temp_ptr = Node() # head_ptr will be the head node of the output list# temp_ptr will be used to insert nodes in the output list# Loop for merging two lists# Loop terminates when both lists reaches to its endwhile List_1 or List_2:# List_1 has not reached its end# and List_2 has either reached its end or its current node has data# greater than or equal to the data of List_1 node# than insert List_1 node in the ouput listif List_1 and (not List_2 or List_1.data <= List_2.data):temp_ptr.next = Node(List_1.data)List_1 = List_1.next# otherwise insert List_2 node in the ouput listelse:temp_ptr.next = Node(List_2.data)List_2 = List_2.next# move temp_pointer to next positiontemp_ptr = temp_ptr.next# return output listreturn head_ptr.next#----------------------------------------------------------## Test merge() function# Linked List with even numbersLL1 = LinkedList()LL1.insert(2)LL1.insert(4)LL1.insert(6)LL1.insert(8)# Linked List with odd numbersLL2 = LinkedList()LL2.insert(1)LL2.insert(3)LL2.insert(5)LL2.insert(7)# Merge FunctionLL3 = LinkedList()LL3.head=merge(LL1.head, LL2.head)LL3.printLL()