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

admin

题目：反向输出一个链表。
程序分析：无。

1. class Node:
   : s' j' m& a& q2 @
2. 
   + R# G7 @! C- R) p2 O+ I: Q
3.     def __init__(self, data):
   5 K+ ?7 n7 \% p7 J2 d
4.         self.data = data
   ( u& S% y' t; I
5.         self.next = None
   
6. 
   5 }  A3 m& U  Z/ C: u  r; d
7.     def get_data(self):
   * k( `/ i% U1 a& A
8.         return self.data
   $ _# d* M1 t4 W: ?) ^
9. 
   1 _3 l. r' z% m; n. }
10. class List:
    2 h' o- g7 t' A1 ~. m  N! F4 B) Y* O
11. 
    ! x* O3 b5 N& M) d4 ?% e
12.     def __init__(self, head):
    $ i1 ^0 I! p" v( o# ~9 Y, m
13.         self.head = head
    , g4 _" x2 D: |9 d# }% @4 G
14. 
    ; e1 x- }7 p2 x2 }6 M; D
15.     def is_empty(self):
    
16.         return self.get_len() == 0
    / [2 q/ i0 K5 E4 G2 d9 H7 L. Z
17. 
    
18.     def get_len(self):  
    
19.         length = 0
    
20.         temp = self.head
    $ D8 a' w+ H0 k% ?( G# B
21.         while temp is not None:
    
22.             length += 1
    8 H8 e' v0 `! e. w+ p
23.             temp = temp.next
    
24.         return length
      m( N, M0 b( n0 e! U
25. 
    7 }% k! P% a  i' u5 G
26.     def append(self, node):
    : H6 }! p7 g* W" t
27.         temp = self.head
    
28.         while temp.next is not None:
    
29.             temp = temp.next
    ) H  d& u$ G0 k
30.         temp.next = node
    + s. f5 N) |" B7 c+ ~5 y
31. 
    % k7 I  q2 I, M6 l
32.     def delete(self, index):
    . s1 E2 \5 W; k' ?  ]6 V
33.         if index < 1 or index > self.get_len():
    - n5 w# d: C5 u1 d/ r  B& U
34.             print("给定位置不合理")
    3 a! C' f" r2 W$ ^4 E8 J. ~+ O
35.             return
    
36.         if index == 1:
    
37.             self.head = self.head.next
    ; j5 f! j2 l2 V: c  U4 y
38.             return
    ( k6 ]: @% e& K; K& y; [
39.         temp = self.head
    
40.         cur_pos = 0
    
41.         while temp is not None:
    # g; H# ^9 m) R4 i) v$ @; N
42.             cur_pos += 1
    7 q5 D5 `$ ^5 i( p
43.             if cur_pos == index-1:
    + @3 \1 o* X; k! M! `, K
44.                 temp.next = temp.next.next
    5 G+ S9 L: w3 p7 @5 c. _
45.             temp = temp.next
    5 a) t" H' u3 c1 F) R0 S3 I
46. 
    7 ^; }; B- r" x; E4 }
47.     def insert(self, pos, node):
    % ]' Y8 p. @1 }8 d$ U6 C$ H# }
48.         if pos < 1 or pos > self.get_len():
    
49.             print("插入结点位置不合理")
    
50.             return
    % d( A6 I0 S( ~1 s. Y
51.         temp = self.head
    
52.         cur_pos = 0
    
53.         while temp is not Node:
    : |  A6 ^. r8 N. @; e, x, \: ?' `
54.             cur_pos += 1
    + d, s* _/ u1 r
55.             if cur_pos == pos-1:
    
56.                 node.next = temp.next
    $ ?8 R& K' \2 ~1 u( }( N( Y2 M
57.                 temp.next =node
    % _) D% x" |5 ?8 J, O" u; {
58.                 break
    
59.             temp = temp.next
    
60. 
    
61.     def reverse(self, head):
    
62.         if head is None and head.next is None:
    5 P: C, J. @4 S7 }+ _
63.             return head
    
64.         pre = head
    
65.         cur = head.next
    
66.         while cur is not None:
    ' k* Y: q# b( @* ?* W5 {
67.             temp = cur.next
    
68.             cur.next = pre
    
69.             pre = cur
    
70.             cur = temp
    
71.         head.next = None
    
72.         return pre
    7 i4 z8 y7 B3 k4 ^
73. 
    
74.     def print_list(self, head):
    
75.         init_data = []
    
76.         while head is not None:
    . o, h/ P- g( o, ?4 w
77.             init_data.append(head.get_data())
    ) ~; ?" n* W5 k# C, b# C
78.             head = head.next
    
79.         return init_data
    
80. 
    ! Z/ ~( O$ D% A* N
81. if __name__=='__main__':
    ; @7 R6 T" m; g8 a' y
82.     head=Node('head')
    
83.     link=List(head)
    
84.     for i in range(10):
    , ^1 W/ K1 `( D2 |' p  V! o$ b- @
85.         node=Node(i)
    
86.         link.append(node)
    / L. ~2 ]# \- D/ ^
87.     print(link.print_list(head))
    ' l# a6 N" o' Z4 U
88.     print(link.print_list(link.reverse(head)))

复制代码