Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # program to merge 2 sorted Linked Lists
- class LinkedList:
- def __init__(self):
- self.head = None
- # returns True is LinkedList is Empty
- def isEmpty(self):
- if self.head is None:
- return True
- else:
- return False
- # method adds elements to the left of the Linked List
- def addToStart(self, data):
- # create a temporary node
- tempNode = Node(data)
- tempNode.setLink(self.head)
- self.head = tempNode
- del tempNode
- # method adds elements to the right of the Linked List
- def addToEnd(self, data):
- start = self.head
- tempNode = Node(data)
- while start.getNextNode():
- start = start.getNextNode()
- start.setLink(tempNode)
- del tempNode
- return True
- # method displays Linked List
- def display(self):
- start = self.head
- if start is None:
- print("Empty List!!!")
- return False
- while start:
- print(str(start.getData()), end=" ")
- start = start.link
- if start:
- print("-->", end=" ")
- print()
- # node class
- class Node:
- # default value of data and link is none if no data is passed
- def __init__(self, data=None, link=None):
- self.data = data
- self.link = link
- # method to update the data feild of Node
- def updateData(self, data):
- self.data = data
- # method to set Link feild the Node
- def setLink(self, node):
- self.link = node
- # method returns data feild of the Node
- def getData(self):
- return self.data
- # method returns address of the next Node
- def getNextNode(self):
- return self.link
- # function to merge 2 sorted linked lists
- def merge(head1, head2):
- head = None
- current = None
- curr1 = head1
- curr2 = head2
- # while both the list are not empty keep merging them
- # exit loop when one of the list has been traversed completly
- while curr1 is not None and curr2 is not None:
- if curr1.getData() > curr2.getData():
- if head is None:
- head = curr2
- current = head
- else:
- current.setLink(curr2)
- current = current.getNextNode()
- curr2 = curr2.getNextNode()
- else:
- if head is None:
- head = curr1
- current = head
- else:
- current.setLink(curr1)
- current = current.getNextNode()
- curr1 = curr1.getNextNode()
- # checking if the first list is not empty then append it the the final list
- if curr1 is not None:
- current.setLink(curr1)
- current = current.getNextNode()
- # checking if the second list is not empty then append it the the final list
- if curr2 is not None:
- current.setLink(curr2)
- current = current.getNextNode()
- return head
- # main method
- print("Program to merge 2 sorted Linked List")
- # creating LinkedList
- myList = LinkedList()
- myList.addToStart(1)
- myList.addToEnd(2)
- myList.addToEnd(3)
- myList.addToEnd(4)
- myList.addToEnd(5)
- myList.addToEnd(6)
- myList.addToEnd(7)
- myList.addToEnd(8)
- myList.addToEnd(9)
- myList.addToEnd(10)
- myList.addToEnd(11)
- print("The first Linked list is : ")
- myList.display()
- myList2 = LinkedList()
- myList2.addToStart(2)
- myList2.addToEnd(4)
- myList2.addToEnd(6)
- myList2.addToEnd(8)
- print("\nThe second Linked list is : ")
- myList2.display()
- print("\nMerged Linked List is : ")
- myList.head = merge(myList.head, myList2.head)
- myList.display()
Add Comment
Please, Sign In to add comment