m2skills

merge sorted ll python

Jan 28th, 2018
33
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 3.16 KB | None | 0 0
  1. # program to merge 2 sorted Linked Lists
  2.  
  3. class LinkedList:
  4.     def __init__(self):
  5.         self.head = None
  6.  
  7.     # returns True is LinkedList is Empty
  8.     def isEmpty(self):
  9.         if self.head is None:
  10.             return True
  11.         else:
  12.             return False
  13.  
  14.     # method adds elements to the left of the Linked List
  15.     def addToStart(self, data):
  16.         # create a temporary node
  17.         tempNode = Node(data)
  18.         tempNode.setLink(self.head)
  19.         self.head = tempNode
  20.         del tempNode
  21.  
  22.     # method adds elements to the right of the Linked List
  23.     def addToEnd(self, data):
  24.         start = self.head
  25.         tempNode = Node(data)
  26.         while start.getNextNode():
  27.             start = start.getNextNode()
  28.         start.setLink(tempNode)
  29.         del tempNode
  30.         return True
  31.  
  32.     # method displays Linked List
  33.     def display(self):
  34.         start = self.head
  35.         if start is None:
  36.             print("Empty List!!!")
  37.             return False
  38.  
  39.         while start:
  40.             print(str(start.getData()), end=" ")
  41.             start = start.link
  42.             if start:
  43.                 print("-->", end=" ")
  44.         print()
  45.  
  46.  
  47. # node class
  48. class Node:
  49.     # default value of data and link is none if no data is passed
  50.     def __init__(self, data=None, link=None):
  51.         self.data = data
  52.         self.link = link
  53.  
  54.     # method to update the data feild of Node
  55.     def updateData(self, data):
  56.         self.data = data
  57.  
  58.     # method to set Link feild the Node
  59.     def setLink(self, node):
  60.         self.link = node
  61.  
  62.     # method returns data feild of the Node
  63.     def getData(self):
  64.         return self.data
  65.  
  66.     # method returns address of the next Node
  67.     def getNextNode(self):
  68.         return self.link
  69.  
  70.  
  71. # function to merge 2 sorted linked lists
  72. def merge(head1, head2):
  73.     head = None
  74.     current = None
  75.     curr1 = head1
  76.     curr2 = head2
  77.  
  78.     # while both the list are not empty keep merging them
  79.     # exit loop when one of the list has been traversed completly
  80.     while curr1 is not None and curr2 is not None:
  81.         if curr1.getData() > curr2.getData():
  82.             if head is None:
  83.                 head = curr2
  84.                 current = head
  85.             else:
  86.                 current.setLink(curr2)
  87.                 current = current.getNextNode()
  88.  
  89.             curr2 = curr2.getNextNode()
  90.  
  91.         else:
  92.             if head is None:
  93.                 head = curr1
  94.                 current = head
  95.             else:
  96.                 current.setLink(curr1)
  97.                 current = current.getNextNode()
  98.  
  99.             curr1 = curr1.getNextNode()
  100.  
  101.     # checking if the first list is not empty then append it the the final list
  102.     if curr1 is not None:
  103.         current.setLink(curr1)
  104.         current = current.getNextNode()
  105.  
  106.     # checking if the second list is not empty then append it the the final list
  107.     if curr2 is not None:
  108.         current.setLink(curr2)
  109.         current = current.getNextNode()
  110.    
  111.     return head
  112.  
  113.  
  114.  
  115.  
  116. # main method
  117. print("Program to merge 2 sorted Linked List")
  118. # creating LinkedList
  119. myList = LinkedList()
  120. myList.addToStart(1)
  121. myList.addToEnd(2)
  122. myList.addToEnd(3)
  123. myList.addToEnd(4)
  124. myList.addToEnd(5)
  125. myList.addToEnd(6)
  126. myList.addToEnd(7)
  127. myList.addToEnd(8)
  128. myList.addToEnd(9)
  129. myList.addToEnd(10)
  130. myList.addToEnd(11)
  131.  
  132. print("The first Linked list is : ")
  133. myList.display()
  134.  
  135. myList2 = LinkedList()
  136.  
  137. myList2.addToStart(2)
  138. myList2.addToEnd(4)
  139. myList2.addToEnd(6)
  140. myList2.addToEnd(8)
  141. print("\nThe second Linked list is : ")
  142. myList2.display()
  143.  
  144. print("\nMerged Linked List is : ")
  145. myList.head = merge(myList.head, myList2.head)
  146. myList.display()
Add Comment
Please, Sign In to add comment