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

admin

题目：反向输出一个链表。
程序分析：无。
/ D* r* n4 w1 M: r9 v% b% N- H1 m: [0 `

1. class Node:
   # C8 c7 q0 w3 @
2. 
   
3.     def __init__(self, data):
   
4.         self.data = data
   9 i; R2 f. ^( g; k
5.         self.next = None
   
6. 
   ' g, f0 t! u( |  Y/ P, C/ v
7.     def get_data(self):
   
8.         return self.data
   
9. 
   
10. class List:
    
11. 
    
12.     def __init__(self, head):
    ; t4 `! z$ A5 J0 i" x/ L) c! s
13.         self.head = head
    , s. `. D$ \2 h' ^3 B2 Q
14. 
    * S5 w9 Z+ \' k# R: h3 @
15.     def is_empty(self):
    
16.         return self.get_len() == 0
    & Z' X  T5 S3 @  s
17. 
    7 H" H1 q* h# _) f$ j
18.     def get_len(self):  
    
19.         length = 0
    
20.         temp = self.head
    . }3 J- `: t$ F1 ?/ |' s2 X7 p
21.         while temp is not None:
    7 e* |1 P8 \: Z/ G; z- u+ F  n! q
22.             length += 1
    / ~/ V. O7 h9 y) j- Q! P
23.             temp = temp.next
    
24.         return length
    & {5 B" S! R4 q9 ?
25. 
    
26.     def append(self, node):
    
27.         temp = self.head
    
28.         while temp.next is not None:
    
29.             temp = temp.next
    - ~: d9 e" \) l6 Y5 l9 K
30.         temp.next = node
    
31. 
    ; G7 W! }- \  f% a& f
32.     def delete(self, index):
    
33.         if index < 1 or index > self.get_len():
    7 p7 p) k9 L% M7 |6 V
34.             print("给定位置不合理")
    
35.             return
    
36.         if index == 1:
    
37.             self.head = self.head.next
    
38.             return
    
39.         temp = self.head
    
40.         cur_pos = 0
    
41.         while temp is not None:
    $ c! y2 T, U, P* |! q
42.             cur_pos += 1
    / }- I2 p) R' ^% R+ [
43.             if cur_pos == index-1:
    6 I+ }) ~! e; m6 I
44.                 temp.next = temp.next.next
    
45.             temp = temp.next
    , H1 t9 M# z8 K( n* a9 @
46. 
    
47.     def insert(self, pos, node):
    
48.         if pos < 1 or pos > self.get_len():
    , g4 s/ K& P% W+ {
49.             print("插入结点位置不合理")
    / i& H8 }- b' w. s! f$ }
50.             return
    
51.         temp = self.head
      ]8 O0 u3 L7 `
52.         cur_pos = 0
    
53.         while temp is not Node:
    
54.             cur_pos += 1
    6 O; e, a6 q4 d: {, C/ o1 [& y! T
55.             if cur_pos == pos-1:
    
56.                 node.next = temp.next
    
57.                 temp.next =node
    ( e! N# i7 o% ?  u" B# B
58.                 break
    7 d7 K# f7 ~) T
59.             temp = temp.next
    * }0 |) p1 V$ H( S) w% q& b" I( W
60. 
    
61.     def reverse(self, head):
    * k5 i7 {  b# A
62.         if head is None and head.next is None:
    ! H; Q5 @. ]3 a& }4 y
63.             return head
    ) [; e" d  c: S4 v# k& F
64.         pre = head
    
65.         cur = head.next
    
66.         while cur is not None:
    
67.             temp = cur.next
    
68.             cur.next = pre
    $ u& f" r; e) v! W' `+ z
69.             pre = cur
    
70.             cur = temp
    / Z; t) E* m5 U1 s: P$ H2 f) @: K
71.         head.next = None
    / i. e8 V9 e% _; q0 m7 I2 V
72.         return pre
    
73. 
    2 Z9 \% `7 e: C; U7 M& z+ S
74.     def print_list(self, head):
    / T& t, p" R( s$ b  Y5 p
75.         init_data = []
    5 I# U" R, ]( d- a0 o" @+ }: e
76.         while head is not None:
    3 I# V7 [! [! w! [
77.             init_data.append(head.get_data())
    + r. f+ |3 H$ X$ f# b
78.             head = head.next
    
79.         return init_data
    , m( R2 @! k% M' ^9 i+ r( y1 L- I
80. 
    8 o- \5 w/ ?" K7 E; k5 @
81. if __name__=='__main__':
    2 r8 b) l9 B3 M/ v9 O! ?
82.     head=Node('head')
    
83.     link=List(head)
    
84.     for i in range(10):
      l, K6 q1 S: i1 d2 u6 A" P; C
85.         node=Node(i)
    
86.         link.append(node)
    
87.     print(link.print_list(head))
    8 ~3 q0 b  j' U( Z
88.     print(link.print_list(link.reverse(head)))

复制代码