两种方法
1,利用栈的方法实现
将节点里的值按顺序 push 压入到栈中
再将 pop 出栈的值按顺序赋值到节点里
2. 原链表头节点删除 再 头插入到一个新的链表里 实现反转
- 1 #!/usr/bin/env python3
- 2
- 3 class Stack(object):
- 4 def __init__(self):
- 5 self._elems = []
- 6
- 7 def is_empty(self):
- 8 return self._elems == []
- 9
- 10 def push(self, elem):
- 11 self._elems.append(elem)
- 12
- 13 def pop(self):
- 14 if self.is_empty():
- 15 raise ValueError("Stack is Empty")
- 16 return self._elems.pop()
- 17
- 18 def peek(self):
- 19 if self.is_empty():
- 20 raise ValueError("Stack is Empty")
- 21 return self._elems[-1]
- 22
- 23 def bianli(self):
- 24 return self._elems
- 25
- 26 class Node(object):
- 27 def __init__(self, elem, next_=None):
- 28 self.elem = elem
- 29 self.next = next_
- 30
- 31 class Simple_List(object):
- 32 def __init__(self):
- 33 self.head = None
- 34 self.rear = None
- 35
- 36 def is_empty(self):
- 37 return self.head is None
- 38
- 39 def prepend(self, elem):
- if self.head is None:
- 40 self.head = Node(elem)
- 41 self.rear = self.head
- 42 else:
- 43 self.head = Node(elem, self.head)
- 44
- 45 def prepop(self):
- 46 if self.head is None:
- 47 raise ValueError("List is Empty")
- 48 e = self.head.elem
- 49 self.head = self.head.next
- 50 return e
- 51
- 52 def append(self, elem):
- 53 if self.head is None:
- 54 self.head = Node(elem)
- 55 self.rear = self.head
- 56 else:
- 57 self.rear = Node(elem)
- 58 self.rear = self.rear.next
- 59
- 60 def pop(self):
- 61 if self.head is None:
- 62 raise ValueError("List is Empty")
- 63 p = self.head
- 64 if p.next is None:
- 65 self.head = None
- 66 while p.next.next:
- 67 p = p.next
- 68 e = p.next.elem
- 69 p.next = None
- 70 self.rear = p
- 71 return e
- 72
- 73 def reverse_stack(self):
- 74 s1 = Stack()
- 75 p = self.head
- 76 while p:
- 77 s1.push(p.elem)
- 78 p = p.next
- 79 p = self.head
- 80 while p:
- 81 p.elem = s1.pop()
- 82 p = p.next
- 83
- 84 def reverse(self):
- 85 li = Simple_List()
- 86 while not self.is_empty():
- 87 li.prepend(self.prepop())
- 88 return li
- 89
- 90 def bianli(self):
- 91 p = self.head
- 92 li = []
- 93 while p:
- 94 li.append(p.elem)
- 95 p = p.next
- 96 return li
- 97
- 98 if __name__=='__main__':
- 99 l = Simple_List()
- 100 for i in range(10):
- 101 l.prepend(i)
- 102 print("origin list:",l.bianli())
- 103 l.reverse_stack()
- 104 print("stack reverse:",l.bianli())
- 105 print("prepend and prepop reverse:",l.reverse().bianli())
来源: http://www.bubuko.com/infodetail-1955831.html