Advertisement
Guest User

Untitled

a guest
Jul 27th, 2017
54
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.29 KB | None | 0 0
  1. def reverse (item, tail = None):
  2. next = item.next
  3. item.next = tail
  4. if next is None:
  5. return item
  6. else:
  7. return reverse(next, item)
  8.  
  9. class LinkedList:
  10. def __init__ (self, value, next = None):
  11. self.value = value
  12. self.next = next
  13. def __repr__ (self):
  14. return 'LinkedList({}, {})'.format(self.value, repr(self.next))
  15.  
  16. >>> a = LinkedList(1, LinkedList(2, LinkedList(3, LinkedList(4))))
  17. >>> a
  18. LinkedList(1, LinkedList(2, LinkedList(3, LinkedList(4, None))))
  19. >>> b = reverse(a)
  20. >>> b
  21. LinkedList(4, LinkedList(3, LinkedList(2, LinkedList(1, None))))
  22. >>> a # note that there is a new head pointer now
  23. LinkedList(1, None)
  24.  
  25. def reverse(head):
  26. # Empty list is always None
  27. if not head:
  28. return None
  29.  
  30. # List of length 1 is already reversed
  31. if not head.get_next():
  32. return head
  33.  
  34.  
  35. next = head.get_next()
  36.  
  37. head.set_next(None)
  38.  
  39. rest = reverse(next)
  40.  
  41. next.set_next(head)
  42.  
  43. return rest
  44.  
  45. class Node(object):
  46. def __init__(self,initdata):
  47. self.data = initdata
  48. self.next = None
  49.  
  50. def getData(self):
  51. return self.data
  52.  
  53. def getNext(self):
  54. return self.next
  55.  
  56. def setData(self,newdata):
  57. self.data = newdata
  58.  
  59. def setNext(self,newnext):
  60. self.next = newnext
  61.  
  62. class LinkedList(object):
  63. def __init__(self):
  64. self.head = None
  65.  
  66. def isEmpty(self):
  67. return self.head == None
  68.  
  69. def add(self,data): #this method adds node at head
  70. temp = Node(data)
  71. temp.setNext(self.head)
  72. self.head = temp
  73.  
  74. def traverse(self):
  75. current = self.head
  76. while current:
  77. if current.getNext():
  78. print(current.data,end="->")
  79. else:
  80. print(current.data)
  81. current = current.getNext()
  82.  
  83. def reverse(self,item):
  84. if item.getNext() == None:
  85. self.head = item
  86. return
  87. self.reverse(item.getNext())
  88. temp = item.getNext()
  89. temp.next = item
  90. item.next = None
  91.  
  92.  
  93. def main():
  94. mylist = LinkedList()
  95. mylist.add(15)
  96. mylist.add(20)
  97. mylist.add(25)
  98. mylist.add(30)
  99. mylist.traverse()
  100. mylist.reverse(mylist.head)
  101. mylist.traverse()
  102. print(mylist.head.data)
  103.  
  104. if __name__ == "__main__":
  105. main()
  106.  
  107. Before:
  108. 30->25->20->15
  109. After:
  110. 15->20->25->30
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement