Merge two sorted linked lists
Data Structures and Algorithms Note
how I would do
Always draw for linked list questions then you will find the solution flow.
First of all, we create a dummy node in order to store the result, compare the first node between L1 and L2, let the smaller one be the dummy node.next, so that we know the new linked list starts from the dummy node.next and after finish combines two linked list, we could return the new linked list head by calling dummy node.next.
Compare the rest nodes of two linked lists one by one, link the smaller one to the new linked list and pointer go to the next node of that link, looping the action until one of them reached the last node. Then the other linked list, which hasn’t reached the end and still has some nodes, could be connected directly behind the new linked list.
# Node class
class Node:# Function to initialize the node object
def __init__(self, data):
self.data = data # Assign data
self.next = None # Initialize next as null
# Linked List class
class LinkedList:
# Function to initialize the Linked List object
def __init__(self):
self.head = None
def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
def printList(self):
temp = self.head
while temp:
print(temp.data)
temp = temp.next
def merge_linkedlist(l1,l2):
temp1 = l1
temp2 = l2
# A dummy node to store the result
dummyNode = Node(0)
curr = dummyNode while temp1 is not None and temp2 is not None:
if temp1.data > temp2.data:
curr.next = temp2
curr = temp2
temp2 = temp2.next
else:
curr.next = temp1
curr = temp1
temp1 = temp1.next
if temp1 is not None:
curr.next = temp1
else:
curr.next = temp2
return dummyNode.next
# Create 2 lists
listA = LinkedList()
listB = LinkedList()
# Add elements to the list in sorted order
listA.push(15)
listA.push(10)
listA.push(5)listB.push(20)
listB.push(3)
listB.push(2)listA.head = merge_linkedlist(listA.head, listB.head)
listA.printList()
Time Complexity: O(m+n)
