题目标题

如何实现一个高效的单向链表逆序输出

参考解析
  1. class Node:#定义节点
  2. def __init__(self, initdata):
  3. self.__data = initdata
  4. self.__next = None
  5. def getData(self):
  6. return self.__data
  7. def getNext(self):
  8. return self.__next
  9. def setData(self, newdata):
  10. self.__data = newdata
  11. def setNext(self, newnext):
  12. self.__next = newnext
  13. class SinCycLinkedlist:
  14. def __init__(self):
  15. self.head = Node(None)
  16. self.head.setNext(self.head)
  17. def add(self, item):
  18. temp = Node(item)
  19. temp.setNext(self.head.getNext())
  20. self.head.setNext(temp)
  21. def reverse(self):
  22. header =self.head
  23. if header == None or header.getNext().getData() == None:
  24. pass
  25. p1 = header #p1,p2,p3就相当于C语言里的三个指针
  26. p2 = p1.getNext()
  27. while(p2.getData()!=None):
  28. p3 = p2.getNext()
  29. p2.setNext(p1)
  30. p1 = p2
  31. p2 = p3
  32. header.setNext(None)
  33. header = p1
  34. self.head.setData(None)
  35. self.head.setNext(p1)
  36. def print_list(self):
  37. l = []
  38. p =self.head
  39. if p.getData()!= None:
  40. l.append(p.getData())
  41. while (p.getNext().getData()!= None):
  42. p = p.getNext()
  43. l.append(p.getData())
  44. print l
  45. if __name__ == '__main__':
  46. s = SinCycLinkedlist()
  47. s.add(10)
  48. s.add(9)
  49. s.add(8)
  50. s.add(7)
  51. s.add(6)
  52. s.add(5)
  53. s.print_list()
  54. p =s.head
  55. s.reverse()
  56. print "After reverse..."
  57. s.print_list()