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

admin

题目：反向输出一个链表。
程序分析：无。
: K1 |' ^# A7 k6 h

1. class Node:
   / U# R3 G1 v( D1 D- Z9 S5 }
2. 
   
3.     def __init__(self, data):
   
4.         self.data = data
   ; ~8 L: C1 G. {6 n
5.         self.next = None
   
6. 
   + f7 s1 H- t: M
7.     def get_data(self):
   
8.         return self.data
   
9. 
   
10. class List:
    - M# F* B% e' i3 R/ y
11. 
    # L. B1 L$ |, J. e1 p. Q
12.     def __init__(self, head):
    
13.         self.head = head
    ' @6 a% ?0 p/ N8 I; k
14. 
    / U1 x% u6 w; Q0 w% h* f
15.     def is_empty(self):
    
16.         return self.get_len() == 0
    + _, ^! D8 O4 ?  H
17. 
    2 x( x5 _* R0 b+ ~  Z+ c6 x
18.     def get_len(self):  
    
19.         length = 0
    / }) D$ C) K( K2 P1 L' U: g6 ?5 I
20.         temp = self.head
    $ i9 d) G) }( }3 X8 e
21.         while temp is not None:
    
22.             length += 1
    & i3 i! r8 k, Y
23.             temp = temp.next
    , Z9 q" Q, k9 B  q, a0 [
24.         return length
    9 Y" C  c) c) L& l9 o
25. 
    
26.     def append(self, node):
    
27.         temp = self.head
    : L1 U& c0 ?) ?* _% s
28.         while temp.next is not None:
    $ s# w! B. m1 g4 D6 o# k
29.             temp = temp.next
    
30.         temp.next = node
    ! [4 {: p. n2 i# |% A, {
31. 
    
32.     def delete(self, index):
    8 k2 v. x( B5 I' Z, Z
33.         if index < 1 or index > self.get_len():
    # r* e+ \/ |. M7 p" _# s; p' Y$ b+ f
34.             print("给定位置不合理")
    # ]  E8 b: G# i
35.             return
    
36.         if index == 1:
    $ O7 [9 u" ~7 n
37.             self.head = self.head.next
    . m  e2 j$ G% x4 K$ I$ u9 Q/ w+ D
38.             return
    * B% u6 Z' d: c/ g4 X: g$ p' x
39.         temp = self.head
    
40.         cur_pos = 0
    8 ]7 r+ L2 {9 f' N+ e! D
41.         while temp is not None:
    
42.             cur_pos += 1
    7 e2 f; g; }* U# n' N$ A4 }
43.             if cur_pos == index-1:
    0 o6 `4 ]* {7 F3 L5 I
44.                 temp.next = temp.next.next
    , }# i. e# h+ Q+ T
45.             temp = temp.next
    * U- H! L0 Y; e
46. 
    ) d( C% l0 t( K: `' i4 ^
47.     def insert(self, pos, node):
    
48.         if pos < 1 or pos > self.get_len():
    
49.             print("插入结点位置不合理")
    3 b# s5 [* y$ U
50.             return
    % O" n7 J9 }$ I* O6 H( U# O
51.         temp = self.head
    - M; K( R) V% J
52.         cur_pos = 0
    
53.         while temp is not Node:
    
54.             cur_pos += 1
    7 B( }6 l: Z' v2 {
55.             if cur_pos == pos-1:
    
56.                 node.next = temp.next
    
57.                 temp.next =node
    
58.                 break
    , p% o" }7 A; g) ?. |; `! o0 Y
59.             temp = temp.next
    9 ~  ?+ {2 N! k0 ]6 {
60. 
    
61.     def reverse(self, head):
    9 O: L$ G  G) o) G) }
62.         if head is None and head.next is None:
    , D! o5 ]7 l; }# B
63.             return head
    : Y7 l8 Q  k5 g0 Y( d: J4 K# i& N
64.         pre = head
    * a! f- ~# `" e/ g
65.         cur = head.next
    
66.         while cur is not None:
    
67.             temp = cur.next
    
68.             cur.next = pre
    ( {* J# t- C  Y8 [  K5 y
69.             pre = cur
    % A6 c  j& v; d  W- G1 E
70.             cur = temp
    
71.         head.next = None
    1 j/ p  @+ H" c& z: M3 ?' v
72.         return pre
    : X: E% X  `/ z& `1 l- m/ A
73. 
    1 O) y8 o# A. t( u% M
74.     def print_list(self, head):
    
75.         init_data = []
    ) {( i2 e- ^9 @# V. ~
76.         while head is not None:
    
77.             init_data.append(head.get_data())
    + T. d! K9 s! _$ j
78.             head = head.next
    
79.         return init_data
    
80. 
    
81. if __name__=='__main__':
    
82.     head=Node('head')
    
83.     link=List(head)
    
84.     for i in range(10):
    ; Q6 W) q2 I0 Y" h0 r6 r
85.         node=Node(i)
    
86.         link.append(node)
    , g& W' x5 z6 {( O
87.     print(link.print_list(head))
    6 ]' b3 i4 J) Q9 z
88.     print(link.print_list(link.reverse(head)))

复制代码