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

admin

题目：反向输出一个链表。
( i1 x$ s3 w$ o2 z: e程序分析：无。
! r" x& g. x0 K3 L

1. class Node:
   1 H3 s0 P) O7 S/ J9 t3 d0 v
2. 
   
3.     def __init__(self, data):
   : y+ J7 X3 @0 K) y3 w
4.         self.data = data
   2 @  X7 S( g& s3 n
5.         self.next = None
   , d% h- x) m3 n5 U
6. 
   
7.     def get_data(self):
   
8.         return self.data
   
9. 
   & x+ \, x; [/ N7 y: S& Q
10. class List:
    4 s: j* R5 l3 b- ^
11. 
    0 q7 b, }. J5 S8 H; T% b
12.     def __init__(self, head):
    
13.         self.head = head
    
14. 
    " q$ T  G" `6 n7 t2 d& V! C
15.     def is_empty(self):
      f6 o, m5 A6 e8 e0 W9 P4 K: V
16.         return self.get_len() == 0
    
17. 
    * e1 \* H5 O+ s) [0 V6 y7 k5 x
18.     def get_len(self):  
    
19.         length = 0
    
20.         temp = self.head
    $ L5 h1 b5 d8 Q
21.         while temp is not None:
    
22.             length += 1
    2 ?9 t4 |3 n) w+ G+ ~
23.             temp = temp.next
    ! N. h- @* L1 d* v) Q# `
24.         return length
    ! _, H3 R% o& W
25. 
    
26.     def append(self, node):
    : j; q* u3 d% {0 G0 V) U8 s+ S
27.         temp = self.head
    6 I  x6 H& x- l
28.         while temp.next is not None:
    
29.             temp = temp.next
    
30.         temp.next = node
    
31. 
    7 ^) o) V, s4 s
32.     def delete(self, index):
    
33.         if index < 1 or index > self.get_len():
    
34.             print("给定位置不合理")
    6 y$ ?! j0 G" k, J! d0 k
35.             return
    8 y* V. Q% k) `( o2 t1 i! R: K$ f
36.         if index == 1:
    " o& \9 y3 i+ X3 l
37.             self.head = self.head.next
    
38.             return
    ! g8 f( J$ q- X$ {' @
39.         temp = self.head
    7 b0 u$ |" D: t$ {6 M( r* x: Z/ Y
40.         cur_pos = 0
    4 G* Z% H) f7 P& v, [7 I5 n1 }
41.         while temp is not None:
    ! [5 I/ `8 U! I8 r9 J
42.             cur_pos += 1
    ) [7 n4 ?0 e  @* Z) o7 l/ C
43.             if cur_pos == index-1:
    
44.                 temp.next = temp.next.next
      x1 J9 U6 a9 \. |
45.             temp = temp.next
    
46. 
    
47.     def insert(self, pos, node):
    
48.         if pos < 1 or pos > self.get_len():
    # |- C/ U6 }* N1 |9 u; e- s
49.             print("插入结点位置不合理")
    ) U7 |4 m$ G- S2 ?) V/ g. I3 r
50.             return
    
51.         temp = self.head
    / X* z' G/ f3 t" N  O
52.         cur_pos = 0
    4 v" v; y' u4 t3 {7 H- c
53.         while temp is not Node:
    
54.             cur_pos += 1
    
55.             if cur_pos == pos-1:
    6 \4 c; N5 o; r2 x+ O  y: H5 j7 S
56.                 node.next = temp.next
    9 T& _3 |* I( E9 g- E2 f! @
57.                 temp.next =node
    0 y% J9 a' S4 n) r6 U* n$ q
58.                 break
    
59.             temp = temp.next
    
60. 
    4 a2 f4 H4 h8 f) h6 X
61.     def reverse(self, head):
    
62.         if head is None and head.next is None:
    
63.             return head
    
64.         pre = head
    
65.         cur = head.next
    
66.         while cur is not None:
    7 v3 J; @) o4 z5 t. Q1 i
67.             temp = cur.next
    
68.             cur.next = pre
    
69.             pre = cur
    6 B8 E1 j: w) a/ |" q$ p
70.             cur = temp
    - Y& Y$ Y: _: o5 F4 I
71.         head.next = None
    
72.         return pre
    
73. 
    % K  a0 r( w5 R+ t+ l+ e
74.     def print_list(self, head):
    - I2 R2 R  N  A) l; Z/ A
75.         init_data = []
    8 y  V! H8 [: Q% E9 a) g9 |
76.         while head is not None:
    5 B1 G/ C. R9 v$ B3 U( p
77.             init_data.append(head.get_data())
    
78.             head = head.next
    
79.         return init_data
    + _# Q' {' P4 C' Z; a6 r
80. 
    $ a- [/ Q% W8 o4 l# @9 q/ Z
81. if __name__=='__main__':
    1 `, S* d1 L* h& Q
82.     head=Node('head')
    
83.     link=List(head)
    
84.     for i in range(10):
    8 N% y& p% r( @  c8 \
85.         node=Node(i)
    
86.         link.append(node)
    , P* ^# t! q  i! b- s% B7 K- ^' q/ u
87.     print(link.print_list(head))
    7 ^4 H- t4 s8 ^
88.     print(link.print_list(link.reverse(head)))

复制代码