7933 - [D]实例073：反向输出链表

admin

题目：反向输出一个链表。
* t# ^* W( L4 }' Y程序分析：无。
7 a$ [- i+ f0 W+ `7 R

1. class Node:
   
2. 
   % I. D$ p3 J$ F8 X5 b! d
3.     def __init__(self, data):
   
4.         self.data = data
   7 q5 x2 D7 z, X  t# u  z
5.         self.next = None
   
6. 
   
7.     def get_data(self):
   
8.         return self.data
   5 }+ M6 k, e# H4 U! c& y
9. 
   7 g# R% c2 E3 n8 V9 Q; n
10. class List:
    
11. 
    
12.     def __init__(self, head):
    & U$ P. S/ k, M
13.         self.head = head
    
14. 
      l% n% n' j9 j$ G4 Z/ Q
15.     def is_empty(self):
    & i9 ?; e2 i8 U3 F
16.         return self.get_len() == 0
    
17. 
    0 L: P* W8 R, u; Q# b2 _" S
18.     def get_len(self):  
    
19.         length = 0
    & w! Y: Z6 F. ~
20.         temp = self.head
    
21.         while temp is not None:
    
22.             length += 1
    ; Z7 t2 k% ?& b: a- A& r
23.             temp = temp.next
      w. O" S( Q2 v4 @: N5 F( P
24.         return length
    
25. 
    
26.     def append(self, node):
    ( {$ Q! N! Q& I
27.         temp = self.head
    3 l4 M2 A0 D2 B) ]( W' S, H
28.         while temp.next is not None:
    
29.             temp = temp.next
    
30.         temp.next = node
    
31. 
    
32.     def delete(self, index):
    : m# i0 K9 v4 D6 o
33.         if index < 1 or index > self.get_len():
    
34.             print("给定位置不合理")
    
35.             return
    ; A3 J; h' j$ a6 B) e) P6 e
36.         if index == 1:
    * V5 C) O! K& t: G* [: w9 c: x& m& c
37.             self.head = self.head.next
    0 m. }7 Z1 t/ C& C( F1 ]  O% G
38.             return
    
39.         temp = self.head
    & X7 T, y- F& x/ n1 r2 z/ H
40.         cur_pos = 0
    ) A' \  ]. z9 X- m) ^! ^
41.         while temp is not None:
    
42.             cur_pos += 1
    * @8 i) u% D* {  N2 Q( ~$ `
43.             if cur_pos == index-1:
    
44.                 temp.next = temp.next.next
    
45.             temp = temp.next
    
46. 
    & z' S# T, L. [/ p
47.     def insert(self, pos, node):
    6 b/ c3 K0 p) |7 q$ O7 E. V. I: s
48.         if pos < 1 or pos > self.get_len():
    + d) p/ ~+ K& K" W0 \; g) I$ ?
49.             print("插入结点位置不合理")
    ) E1 F+ i; h/ k( ^  I0 F+ D
50.             return
    4 w3 u- p6 a) k6 c3 K, ~8 E1 Y
51.         temp = self.head
    3 h' J3 Q. s& G7 ^4 S
52.         cur_pos = 0
    $ P# F8 g6 s0 ]& y' k% Y9 g" H
53.         while temp is not Node:
    
54.             cur_pos += 1
    
55.             if cur_pos == pos-1:
    
56.                 node.next = temp.next
    5 Z% e4 R) a" v7 y: E
57.                 temp.next =node
    " g3 I) m- R$ r; n1 V6 y
58.                 break
    
59.             temp = temp.next
    ! {( t4 w3 Y. q
60. 
    4 t6 @( r2 E4 R3 o! h5 ^7 @
61.     def reverse(self, head):
    
62.         if head is None and head.next is None:
    
63.             return head
    & r/ [; j8 t5 x7 x  R8 V
64.         pre = head
    8 c" h5 U- O3 R
65.         cur = head.next
    ) Q4 ]$ U1 x" B# V$ I/ `! j
66.         while cur is not None:
    / q, K9 I; f; ~" D6 m( o+ V- D8 l
67.             temp = cur.next
    2 V7 }9 S( r$ F
68.             cur.next = pre
    : K* |& g# g5 M) F" y3 U2 n
69.             pre = cur
    
70.             cur = temp
      I1 r1 a- _& ]# m2 G" F) p
71.         head.next = None
    
72.         return pre
    9 j  @" T: b2 n# C' Q8 U& j
73. 
    ) l/ y% q' V' n6 z. n5 k: V) m: b
74.     def print_list(self, head):
    
75.         init_data = []
    * j/ ^; r1 r9 k
76.         while head is not None:
    
77.             init_data.append(head.get_data())
    . t2 W2 R3 H# _; U6 c
78.             head = head.next
    
79.         return init_data
    
80. 
    
81. if __name__=='__main__':
    
82.     head=Node('head')
    ' u+ N: F5 J+ c3 n4 l9 `7 }5 \
83.     link=List(head)
    
84.     for i in range(10):
    
85.         node=Node(i)
    
86.         link.append(node)
    
87.     print(link.print_list(head))
    
88.     print(link.print_list(link.reverse(head)))

复制代码