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

admin

题目：反向输出一个链表。
程序分析：无。
" J6 |% E# F. g2 j7 V9 I# \: b/ k

1. class Node:
   ) f8 J# h8 _. G
2. 
   
3.     def __init__(self, data):
   ) k0 z6 B4 d& X8 b2 p! m2 O
4.         self.data = data
   
5.         self.next = None
   
6. 
   4 {/ d6 S; {3 q
7.     def get_data(self):
   ' I" u6 Q3 s2 I$ h
8.         return self.data
   % L9 A7 `, b. }8 Y
9. 
   
10. class List:
    0 N; F: e9 N1 o. X1 j
11. 
    " L4 Y3 v- K/ ^7 s. M0 u# q- y
12.     def __init__(self, head):
    1 ^1 o, Q  p# U" A
13.         self.head = head
    
14. 
    / w5 e" e9 a% i) ~1 ]! X2 d
15.     def is_empty(self):
    
16.         return self.get_len() == 0
    
17. 
    
18.     def get_len(self):  
    4 L# t, ]9 M. i4 R) a
19.         length = 0
    
20.         temp = self.head
    ( k! ^: w; B5 Y
21.         while temp is not None:
    
22.             length += 1
    
23.             temp = temp.next
    
24.         return length
    3 v$ ^6 L7 W* C3 r9 L# j
25. 
    
26.     def append(self, node):
    % E  F  E+ K! @6 I1 Y
27.         temp = self.head
    ) r8 l# I3 P) g' g9 b3 @& m
28.         while temp.next is not None:
    
29.             temp = temp.next
    5 |: |- P2 N2 X3 K
30.         temp.next = node
    
31. 
    
32.     def delete(self, index):
    , A1 |9 j& ^  Y* b, o
33.         if index < 1 or index > self.get_len():
    : T% x% X- t+ C  J% [: q- I. [( A
34.             print("给定位置不合理")
    
35.             return
    
36.         if index == 1:
    9 h6 X7 b. X0 G
37.             self.head = self.head.next
    
38.             return
    
39.         temp = self.head
    
40.         cur_pos = 0
    
41.         while temp is not None:
    
42.             cur_pos += 1
    
43.             if cur_pos == index-1:
    / h; R5 d1 ?& m5 ~$ s
44.                 temp.next = temp.next.next
    
45.             temp = temp.next
    3 M) R! V0 L0 A6 x2 B
46. 
    
47.     def insert(self, pos, node):
    ; m4 Z- m9 ?$ u) b7 G$ N% V! U
48.         if pos < 1 or pos > self.get_len():
    
49.             print("插入结点位置不合理")
    ! }. }1 o, l, C8 _" c
50.             return
    . I! K6 O& `% B/ l, V- `
51.         temp = self.head
    $ X. J/ `; t! u5 T2 W
52.         cur_pos = 0
    * |) U! z- E# n( g5 d% |
53.         while temp is not Node:
    , N( h+ z6 [. m" t: u0 l/ h. ?5 ]
54.             cur_pos += 1
    
55.             if cur_pos == pos-1:
    
56.                 node.next = temp.next
    
57.                 temp.next =node
    
58.                 break
    6 C' i0 R6 Z, q/ j. h# n
59.             temp = temp.next
    
60. 
    
61.     def reverse(self, head):
    8 a+ t" h; ^7 o2 W' e2 @* B
62.         if head is None and head.next is None:
    ! Y. U! }; L6 m0 c1 K8 T2 K1 ]
63.             return head
    
64.         pre = head
      G2 r7 R2 w" j0 s# _& l
65.         cur = head.next
    5 d2 c9 X" a. o/ z4 i- L1 |
66.         while cur is not None:
    " Y# g4 \+ V. ~8 @# q  M$ b
67.             temp = cur.next
    
68.             cur.next = pre
    3 X  L& E9 p0 o. G0 c
69.             pre = cur
    : W# {! `$ G( ]( ^
70.             cur = temp
    
71.         head.next = None
    
72.         return pre
    
73. 
    6 v, |& a  s- z8 s$ d. D8 ~
74.     def print_list(self, head):
    ' G5 M2 G0 U& |# h% v
75.         init_data = []
    
76.         while head is not None:
    
77.             init_data.append(head.get_data())
    
78.             head = head.next
    
79.         return init_data
    2 e' }% h$ l, O4 F5 j
80. 
    + k8 q# h8 ^3 S) q! u# {3 o8 W( B
81. if __name__=='__main__':
    
82.     head=Node('head')
    
83.     link=List(head)
    + m* {5 p# Q9 g+ R' ^% Q+ Z) ^
84.     for i in range(10):
    2 @4 N3 x: @/ W, a0 s" L
85.         node=Node(i)
    
86.         link.append(node)
    0 c+ a  P! t* D. M4 p
87.     print(link.print_list(head))
    
88.     print(link.print_list(link.reverse(head)))

复制代码