m2skills

reverse starting ll python

Jan 30th, 2018
163
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 2.47 KB | None | 0 0
  1. # program to reverse starting k elements of Linked List
  2.  
  3. class LinkedList:
  4.     def __init__(self):
  5.         self.head = None
  6.  
  7.     # method adds elements to the left of the Linked List
  8.     def addToStart(self, data):
  9.         # create a temporary node
  10.         tempNode = Node(data)
  11.         tempNode.setLink(self.head)
  12.         self.head = tempNode
  13.         del tempNode
  14.  
  15.     # method adds elements to the right of the Linked List
  16.     def addToEnd(self, data):
  17.         start = self.head
  18.         tempNode = Node(data)
  19.         while start.getNextNode():
  20.             start = start.getNextNode()
  21.         start.setLink(tempNode)
  22.         del tempNode
  23.         return True
  24.  
  25.     # method displays Linked List
  26.     def display(self):
  27.         start = self.head
  28.         if start is None:
  29.             print("Empty List!!!")
  30.             return False
  31.  
  32.         while start:
  33.             print(str(start.getData()), end=" ")
  34.             start = start.link
  35.             if start:
  36.                 print("-->", end=" ")
  37.         print()
  38.  
  39.  
  40. # node class
  41. class Node:
  42.     # default value of data and link is none if no data is passed
  43.     def __init__(self, data=None, link=None):
  44.         self.data = data
  45.         self.link = link
  46.  
  47.     # method to update the data feild of Node
  48.     def updateData(self, data):
  49.         self.data = data
  50.  
  51.     # method to set Link feild the Node
  52.     def setLink(self, node):
  53.         self.link = node
  54.  
  55.     # method returns data feild of the Node
  56.     def getData(self):
  57.         return self.data
  58.  
  59.     # method returns address of the next Node
  60.     def getNextNode(self):
  61.         return self.link
  62.  
  63.  
  64. # function to reverse first k nodes of a linked list
  65. def reverse_K_nodes(head, k):
  66.     currentNode = head
  67.     nextNode = None
  68.     prevNode = None
  69.  
  70.     # reverse first k nodes
  71.     while currentNode is not None and k != 0:
  72.         nextNode = currentNode.getNextNode()
  73.         currentNode.setLink(prevNode)
  74.         prevNode = currentNode
  75.         currentNode = nextNode
  76.         k -= 1
  77.  
  78.     # assign head as prevNode
  79.     head = prevNode
  80.     currentNode = head
  81.  
  82.     # join the link between current node and the rest of the linked list
  83.     while currentNode.getNextNode() is not None:
  84.         currentNode = currentNode.getNextNode()
  85.     currentNode.setLink(nextNode)
  86.  
  87.     return head
  88.  
  89.  
  90.  
  91.  
  92. # main method
  93. # creating LinkedList
  94. print("Program to reverse first k nodes of the Linked List")
  95. myList = LinkedList()
  96. myList.addToStart(1)
  97. myList.addToEnd(2)
  98. myList.addToEnd(3)
  99. myList.addToEnd(4)
  100. myList.addToEnd(5)
  101. myList.addToEnd(6)
  102. myList.addToEnd(7)
  103. myList.addToEnd(8)
  104. myList.addToEnd(9)
  105. myList.addToEnd(10)
  106. myList.addToEnd(11)
  107. myList.display()
  108.  
  109. print("Reversing the first 4 nodes of the linked list")
  110. myList.head = reverse_K_nodes(myList.head, 4)
  111.  
  112. myList.display()
Add Comment
Please, Sign In to add comment