Related Tags

merge
python

# How to merge two sorted linked lists in Python

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.

## Algorithm

Let’s understand the algorithm for merging two sorted linked list with the illustration below:

1 of 9

## Code

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 list
class Node:
# constructor
def __init__(self, data = None, next=None):
self.data = data
self.next = next

def __init__(self):

# insertion method for the linked list
def insert(self, data):
newNode = Node(data)
while(current.next):
current = current.next
current.next = newNode
else:

# print method for the linked list
def printLL(self):
while(current):
print(current.data)
current = current.next
#-----------------------Merge function---------------------#
def merge(List_1, List_2):
# 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 end
while 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 list
if 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 list
else:
temp_ptr.next = Node(List_2.data)
List_2 = List_2.next
# move temp_pointer to next position
temp_ptr = temp_ptr.next
# return output list
#----------------------------------------------------------#
# Test merge() function
# Linked List with even numbers
LL1.insert(2)
LL1.insert(4)
LL1.insert(6)
LL1.insert(8)
# Linked List with odd numbers
LL2.insert(1)
LL2.insert(3)
LL2.insert(5)
LL2.insert(7)
# Merge Function
LL3.printLL()

RELATED TAGS

merge
python
RELATED COURSES

View all Courses

Keep Exploring

Learn in-demand tech skills in half the time