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

admin

题目：反向输出一个链表。
0 S9 l% B& H9 m/ y! w$ |5 }; a程序分析：无。

1. class Node:
   
2. 
   
3.     def __init__(self, data):
   " m+ j4 }4 u$ U
4.         self.data = data
   $ h4 D' ]* R4 }8 M
5.         self.next = None
   
6. 
   
7.     def get_data(self):
   
8.         return self.data
   2 K/ S# ^9 s5 k2 r# s
9. 
   
10. class List:
    
11. 
    8 h! U5 l' h/ G% K
12.     def __init__(self, head):
    
13.         self.head = head
    
14. 
      u: j' y" Z: H5 S* }
15.     def is_empty(self):
    
16.         return self.get_len() == 0
    7 O/ S/ ~: ^# N4 k* J, C
17. 
    % l" Q/ P  S5 d" ?0 g$ `* S
18.     def get_len(self):  
    
19.         length = 0
    
20.         temp = self.head
    
21.         while temp is not None:
    ) p( ?' p  c) z* M9 F9 x4 p* [
22.             length += 1
    
23.             temp = temp.next
    
24.         return length
    
25. 
    - V& d) T/ S  K) J
26.     def append(self, node):
    
27.         temp = self.head
    
28.         while temp.next is not None:
    , Z2 N: a2 u1 Q+ `' l. c7 u7 t
29.             temp = temp.next
    7 E% k$ _% D3 ]3 O
30.         temp.next = node
    & E; U- t) }2 p7 Z. }* }5 z
31. 
    . R' N3 c0 l9 b: K; X3 J+ y
32.     def delete(self, index):
    
33.         if index < 1 or index > self.get_len():
    ) Y  q& R/ J3 J
34.             print("给定位置不合理")
    
35.             return
    , y! ?0 S7 J; Z: @
36.         if index == 1:
    
37.             self.head = self.head.next
    ! W$ T3 ^) v4 r' y* X! f6 ?& n% z2 ?
38.             return
    % e( j8 J6 c. }0 s8 e& d* @; F
39.         temp = self.head
    4 t9 j2 Y# g( K. M. @
40.         cur_pos = 0
    
41.         while temp is not None:
    
42.             cur_pos += 1
    9 y. b9 Y4 G# N6 L0 [, a+ d) E
43.             if cur_pos == index-1:
    9 s' O) p3 N" |5 ?, o* W
44.                 temp.next = temp.next.next
    $ m1 Q) }. k/ V- t
45.             temp = temp.next
    
46. 
    $ `! W( J& n$ x
47.     def insert(self, pos, node):
    4 Z2 n/ c  E. n' B! N
48.         if pos < 1 or pos > self.get_len():
    - \3 V/ D3 r! m2 I  s9 s
49.             print("插入结点位置不合理")
    
50.             return
    
51.         temp = self.head
    
52.         cur_pos = 0
    
53.         while temp is not Node:
    / o& h* {0 w: ^7 c& L2 f( e3 z
54.             cur_pos += 1
    , W7 t- G" K$ _& q
55.             if cur_pos == pos-1:
    
56.                 node.next = temp.next
    $ @* r3 `3 t6 C3 R5 ~( ^
57.                 temp.next =node
    
58.                 break
    
59.             temp = temp.next
    
60. 
    
61.     def reverse(self, head):
    
62.         if head is None and head.next is None:
    
63.             return head
    + n! u3 O: C% ]5 F1 O& j# b/ X& w1 N
64.         pre = head
    " N# U3 l9 `5 W) S
65.         cur = head.next
    
66.         while cur is not None:
    1 R1 C5 ?, D; E- Z
67.             temp = cur.next
    
68.             cur.next = pre
    
69.             pre = cur
    4 T& f+ T2 D2 g4 G. @" G
70.             cur = temp
    2 v' Y) D+ f# [
71.         head.next = None
    1 f( y7 u1 _1 j0 [! `/ N
72.         return pre
    
73. 
    * {. D. u6 w+ h9 \5 T8 i' z& {. ~
74.     def print_list(self, head):
    2 q# c6 y# g7 u
75.         init_data = []
    
76.         while head is not None:
    
77.             init_data.append(head.get_data())
    
78.             head = head.next
    
79.         return init_data
    % W. @# f) H0 r' E& k9 a2 B! Z
80. 
    
81. if __name__=='__main__':
    % T4 G) s$ y# T% O# M9 ]: U# R! r
82.     head=Node('head')
    
83.     link=List(head)
    
84.     for i in range(10):
    2 U5 P" S7 d4 y4 n' o; C/ q9 H
85.         node=Node(i)
    
86.         link.append(node)
    
87.     print(link.print_list(head))
    
88.     print(link.print_list(link.reverse(head)))

复制代码