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

admin

题目：反向输出一个链表。
- \$ V; V0 k, n6 E" o2 k5 I程序分析：无。
& t' ~8 V, R8 F5 m1 x9 _$ H/ K

1. class Node:
   8 j7 Y. N4 l( ]1 V  b! O0 q7 c5 J
2. 
   
3.     def __init__(self, data):
   
4.         self.data = data
   # U/ V* k8 \  z  M
5.         self.next = None
   
6. 
   4 _, {2 H$ Q2 t! C7 u
7.     def get_data(self):
   
8.         return self.data
   
9. 
   
10. class List:
    
11. 
    
12.     def __init__(self, head):
    0 Y( K! G+ Y& |' m6 E$ S4 C
13.         self.head = head
      U7 q7 F- m6 F/ b5 K! n
14. 
    9 |7 F6 R* d6 G: Q0 t3 c4 q
15.     def is_empty(self):
    
16.         return self.get_len() == 0
    
17. 
    
18.     def get_len(self):  
    
19.         length = 0
    
20.         temp = self.head
    
21.         while temp is not None:
    
22.             length += 1
    
23.             temp = temp.next
    % P; ^5 O; l7 D8 L3 ?* d
24.         return length
    & k" V# M# l: m2 `6 r/ D3 V: W) A
25. 
    , u# f  Q1 u/ ^6 G$ y, Z. ?' f( t: d! W
26.     def append(self, node):
    * x$ I: }$ f4 U9 k( `
27.         temp = self.head
    
28.         while temp.next is not None:
    
29.             temp = temp.next
    . Z: h- S6 ~0 H9 X+ v  ^
30.         temp.next = node
      H/ m3 z. w7 r; g
31. 
    / r7 S2 o5 u9 M( A0 n* c! H: t/ L; J
32.     def delete(self, index):
    
33.         if index < 1 or index > self.get_len():
    
34.             print("给定位置不合理")
    
35.             return
    + T- t: n/ ^- ^( ]3 y2 u
36.         if index == 1:
    
37.             self.head = self.head.next
    9 ~" ~# i5 i+ P% |5 P" f* F
38.             return
    2 Q+ A8 {5 d! C7 `
39.         temp = self.head
    ; J4 M. v3 L6 I5 F4 R' v5 D# n
40.         cur_pos = 0
    
41.         while temp is not None:
    * n  f; i& X: o
42.             cur_pos += 1
    
43.             if cur_pos == index-1:
    
44.                 temp.next = temp.next.next
    
45.             temp = temp.next
    
46. 
    
47.     def insert(self, pos, node):
    
48.         if pos < 1 or pos > self.get_len():
      y( s7 A" b8 G# {* l4 O1 F+ H
49.             print("插入结点位置不合理")
    & v3 d) N; o8 D2 u, x6 e3 O* c) w
50.             return
    
51.         temp = self.head
    
52.         cur_pos = 0
    8 Q5 v7 Y" ~/ q
53.         while temp is not Node:
    
54.             cur_pos += 1
    6 V' g# X1 r% D
55.             if cur_pos == pos-1:
    5 x* ?0 }# w8 Z& B
56.                 node.next = temp.next
    # \( h$ U( L$ L' k
57.                 temp.next =node
    $ x/ R7 f* F+ I/ @3 J
58.                 break
    
59.             temp = temp.next
    
60. 
    1 H2 l6 q  U& h1 J8 e! p8 P) B
61.     def reverse(self, head):
    % Z8 o' n* H# C/ o* L. B) G! d
62.         if head is None and head.next is None:
    
63.             return head
      h! X. X6 M6 i9 F2 ?8 S
64.         pre = head
    
65.         cur = head.next
    
66.         while cur is not None:
    
67.             temp = cur.next
    ( V8 o* |  ~7 N, Z) V: K
68.             cur.next = pre
    
69.             pre = cur
    $ I! I# F7 ^4 F: D: |$ f
70.             cur = temp
    
71.         head.next = None
    - l: u" F6 a2 V$ Q2 h5 B; V
72.         return pre
    
73. 
    8 [6 m% H; m- M% g, P0 e( P5 B
74.     def print_list(self, head):
    
75.         init_data = []
    5 m* O: U9 V: K% l
76.         while head is not None:
      w# I7 d1 l; W, [4 ^
77.             init_data.append(head.get_data())
    4 o4 E& z: Y: R( ?& O5 i
78.             head = head.next
    * A& |- W8 T- c- n
79.         return init_data
    0 p; @/ z4 D1 Y$ u
80. 
    / j- W, D" U/ q1 u: \+ _& _
81. if __name__=='__main__':
    ' W. a3 n4 C7 z/ r6 J' N" b
82.     head=Node('head')
    ! E: J9 ~4 l' B& Y' K/ e+ L
83.     link=List(head)
    
84.     for i in range(10):
    
85.         node=Node(i)
    ) a7 V" Q$ z% y5 A7 o( N
86.         link.append(node)
    ) l: p* |! A6 f2 I. I" M3 R7 Z+ {
87.     print(link.print_list(head))
    
88.     print(link.print_list(link.reverse(head)))

复制代码