之前写了一个单链表反转，但是使用的新的空间。
这次的反转是不修改原来的结构，直接将节点内的元素进行修改
1 #!/usr/bin/env python3 2 3 class LNode(object): 4 def __init__(self, elem, next_=None): 5 self.elem = elem 6 self.next = next_ 7 8 class ListError(Exception): 9 pass 10 11 class LList(object): 12 def __init__(self): 13 self.head = None 14 self.rear = None 15 self.num = 0 16 17 def is_empty(self): 18 return self.head is None 19 20 def count(self): 21 return self.num 22 23 def prepend(self, elem): 24 if self.head is None: 25 self.head = LNode(elem) 26 self.rear = self.head 27 self.num += 1 28 else: 29 self.head = LNode(elem, self.head) 30 self.num += 1 31 32 def pop(self): 33 if self.head is None: 34 raise ListError 35 e = self.head.elem 36 if self.head.next is None: 37 self.rear = None 38 self.head = None 39 self.num -= 1 40 return e 41 self.head = self.head.next 42 self.num -= 1 43 return e 44 45 def append(self, elem): 46 if self.head is None: 47 self.head = LNode(elem) 48 self.rear = self.head 49 self.num += 1 50 return 51 self.rear.next = LNode(elem) 52 self.rear = self.rear.next 53 self.num += 1 54 55 def pop_last(self): 56 if self.head is None: 57 raise ListError 58 p = self.head 59 if p.next is None: 60 e = p.elem 61 self.head = None 62 self.rear = None 63 self.num -= 1 64 return e 65 while p.next.next: 66 p = p.next 67 e = p.next.elem 68 p.next = None 69 self.rear = p 70 self.num -= 1 71 return e 72 73 def bianli(self): 74 p = self.head 75 li = [] 76 while p: 77 li.append(p.elem) 78 p = p.next 79 return li 80 81 def reverse(self): 82 li = self.bianli() 83 li.sort(reverse=True) 84 p = self.head 85 for i in li: 86 p.elem = i 87 p = p.next 88 89 if __name__ == '__main__': 90 l = LList() 91 l.append(1) 92 l.prepend(2) 93 l.pop() 94 l.pop_last() 95 l.append(2) 96 l.prepend(1) 97 l.append(3) 98 print(l.bianli()) 99 l.reverse()100 print(l.bianli())