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

admin

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

1. class Node:
   
2. 
   
3.     def __init__(self, data):
   ! Y  u% Q* L- c% B9 K0 A$ X- x5 [
4.         self.data = data
   7 A( a9 V4 k% ^  i7 E4 f2 `
5.         self.next = None
   3 K4 F5 y+ g  F! {& K
6. 
   1 r8 t. n% d& r# l" T
7.     def get_data(self):
   
8.         return self.data
   
9. 
   % t  a# q- P% x% b) `6 M$ H
10. class List:
    
11. 
    7 ^3 ?" |) d* a: U5 r4 b+ y
12.     def __init__(self, head):
    
13.         self.head = head
    , k2 E% y; ^6 Y+ @- W2 v, Z
14. 
    4 h* K1 C' z2 u4 q
15.     def is_empty(self):
    
16.         return self.get_len() == 0
    9 Y: P: N* c' U- a* q) Q  o# B
17. 
    
18.     def get_len(self):  
    ) S3 L  Q" l5 n% `6 t0 b8 o
19.         length = 0
    - u( }% ^" _% f; J# D' d* u: w
20.         temp = self.head
    6 D3 }- \' d2 h' t
21.         while temp is not None:
    # m1 M- Q3 _* Y* E8 y1 ~1 O
22.             length += 1
    ( h# a4 c4 b# j5 q1 |. L7 Y# ~
23.             temp = temp.next
    ; R, D9 i+ O$ G# ]0 F% c5 L
24.         return length
    
25. 
    
26.     def append(self, node):
    
27.         temp = self.head
    ) B3 f' x. {6 E/ _7 j
28.         while temp.next is not None:
    
29.             temp = temp.next
    
30.         temp.next = node
    & G% s- |% z# a2 V+ W8 E4 e
31. 
    3 Y8 z) h. N7 V. v  b9 b" N
32.     def delete(self, index):
    . y+ r: A7 X% j2 e
33.         if index < 1 or index > self.get_len():
    
34.             print("给定位置不合理")
    
35.             return
    
36.         if index == 1:
    : P4 s, }6 `" Y/ i" \
37.             self.head = self.head.next
    - k: V- B+ L0 f: n
38.             return
    
39.         temp = self.head
    " q5 b7 Z. {- j0 v1 t0 z0 |
40.         cur_pos = 0
    ' o8 L  u& }# Q! J7 {3 x
41.         while temp is not None:
    8 t: i) X; o# U8 ?+ W
42.             cur_pos += 1
    7 u1 i7 H$ v+ r
43.             if cur_pos == index-1:
    
44.                 temp.next = temp.next.next
    
45.             temp = temp.next
    
46. 
    9 D9 G: ]9 }9 L6 y* z% \# T
47.     def insert(self, pos, node):
    
48.         if pos < 1 or pos > self.get_len():
    
49.             print("插入结点位置不合理")
    5 N; Q8 ^2 s- \8 r
50.             return
    2 U6 q# k5 O. \2 K- E- y" E
51.         temp = self.head
    . }( k8 N3 N3 ]3 T
52.         cur_pos = 0
    
53.         while temp is not Node:
    # a& Y: O" s5 \3 n5 W
54.             cur_pos += 1
    
55.             if cur_pos == pos-1:
    
56.                 node.next = temp.next
    & r( x  E. N7 l8 P9 n6 D
57.                 temp.next =node
    
58.                 break
    % m; \* u( ~: I
59.             temp = temp.next
    4 Y9 E1 l8 N5 ]7 Z0 S. \" n
60. 
    0 Y9 x3 ^: u5 l
61.     def reverse(self, head):
    
62.         if head is None and head.next is None:
    3 V" k! t9 b5 V; @7 l% u
63.             return head
    
64.         pre = head
    
65.         cur = head.next
    8 m/ N8 K$ F( M3 P" X/ U, B
66.         while cur is not None:
    
67.             temp = cur.next
    
68.             cur.next = pre
    : t* Z( b5 n6 }+ i8 r" u" u
69.             pre = cur
    
70.             cur = temp
    / V4 e; n- B2 L: e
71.         head.next = None
    
72.         return pre
    
73. 
    : h" r  Q% |- |
74.     def print_list(self, head):
    7 z% g7 }. N2 t; b
75.         init_data = []
    
76.         while head is not None:
    
77.             init_data.append(head.get_data())
    
78.             head = head.next
    ; _8 A, D) R: ~# J6 \6 @' V( B
79.         return init_data
    ) b- u0 N# t1 @- }
80. 
    : g2 ?( V" K8 M0 Y, u4 t
81. if __name__=='__main__':
    ) j$ |, `. E! r" W8 `1 L
82.     head=Node('head')
    ! u2 D  x" d' l) B. R( a
83.     link=List(head)
    6 R/ p7 y' l. ?
84.     for i in range(10):
    
85.         node=Node(i)
    
86.         link.append(node)
    / m, R* D& o. q/ i3 P/ I( u
87.     print(link.print_list(head))
    
88.     print(link.print_list(link.reverse(head)))

复制代码