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

admin

题目：反向输出一个链表。
1 q' A# Q% J0 F程序分析：无。

1. class Node:
   
2. 
   . d8 H& ?2 {0 |% q. c
3.     def __init__(self, data):
   3 r) g5 s7 I1 a6 k
4.         self.data = data
   
5.         self.next = None
   , J: e( P- I$ `( p5 \
6. 
   # n' C& Q) k: i0 H# J* c" ^
7.     def get_data(self):
   
8.         return self.data
   
9. 
   1 }3 O: r' m" G( k; l4 D& s
10. class List:
    
11. 
    ) d" x$ m1 m  m4 M! r: \
12.     def __init__(self, head):
    & Y' P5 k3 c; a" L) f+ U( |
13.         self.head = head
    / S/ T8 @! Q7 u: W- `; Y- G, _
14. 
    
15.     def is_empty(self):
    2 D  x: b# G" {" Q; o
16.         return self.get_len() == 0
    9 J$ j$ g8 j0 ~) s; b
17. 
    # L+ d9 N: b, X3 q9 q9 c
18.     def get_len(self):  
    
19.         length = 0
    
20.         temp = self.head
      j+ ]+ W+ Y  U0 ]7 c8 }. l
21.         while temp is not None:
    
22.             length += 1
    
23.             temp = temp.next
    
24.         return length
    8 X) {9 Q, k) H. v+ D7 s
25. 
    
26.     def append(self, node):
    9 `! U$ ?0 A4 V+ @& l9 M
27.         temp = self.head
    & Z- V# N: o( y4 q, Z, [
28.         while temp.next is not None:
    , X# Z2 f9 \& K+ Y) g4 c
29.             temp = temp.next
    0 z+ e8 t6 y9 y
30.         temp.next = node
    3 r/ h" i4 ]7 T! U; j, j7 a
31. 
    
32.     def delete(self, index):
    ' w: n9 a+ k( R4 x0 u1 D) N" l
33.         if index < 1 or index > self.get_len():
    ; P- J2 [& l9 w+ {* ?( u
34.             print("给定位置不合理")
    
35.             return
    3 Z1 q9 j8 w1 z. @* U' a! ?! B* Q
36.         if index == 1:
    " M7 n7 p; D2 k7 Y' S; q, [0 @, Q
37.             self.head = self.head.next
    0 D( f# a6 |+ w3 Z* r
38.             return
    
39.         temp = self.head
    
40.         cur_pos = 0
    
41.         while temp is not None:
    
42.             cur_pos += 1
    
43.             if cur_pos == index-1:
    
44.                 temp.next = temp.next.next
    8 x+ @2 b, F! {8 B* q5 ]
45.             temp = temp.next
    6 i/ I; G" @( b% w. C
46. 
    
47.     def insert(self, pos, node):
    
48.         if pos < 1 or pos > self.get_len():
    * m8 n  p( K& j6 g
49.             print("插入结点位置不合理")
    
50.             return
    
51.         temp = self.head
    
52.         cur_pos = 0
    6 h: U  r3 b1 l; A9 m0 C
53.         while temp is not Node:
    
54.             cur_pos += 1
    
55.             if cur_pos == pos-1:
    
56.                 node.next = temp.next
    
57.                 temp.next =node
    
58.                 break
    2 K0 o- ~- s2 k% G4 k
59.             temp = temp.next
    8 n1 b; U# E* f0 X7 S; D
60. 
    5 K( t; i( Y# C- E& [1 G2 B8 L% R
61.     def reverse(self, head):
    
62.         if head is None and head.next is None:
    * F3 b7 d% X4 ^- q* b$ f' _
63.             return head
    / }: D0 _: s' r1 B- O. F) ?4 u
64.         pre = head
    2 F6 \  D9 T; _$ l7 b2 ^- A
65.         cur = head.next
    
66.         while cur is not None:
    $ }3 H1 J+ u7 s& M  v  a0 J
67.             temp = cur.next
    
68.             cur.next = pre
    
69.             pre = cur
    ! u! C. x. z9 D6 b: B- M3 E
70.             cur = temp
    
71.         head.next = None
    . X! e! \) q1 H$ ~6 _' [
72.         return pre
    , F: n$ B$ a) c5 `  k" |
73. 
    4 @# H9 v/ g5 @9 R: f: M, h
74.     def print_list(self, head):
    
75.         init_data = []
    
76.         while head is not None:
    
77.             init_data.append(head.get_data())
    + r" _$ P/ m3 F  t7 u% G( r9 P
78.             head = head.next
    * [; B3 ?0 s0 ?/ d% F% J& R. V
79.         return init_data
    
80. 
    " f; b- u3 k  F# Y6 P3 k
81. if __name__=='__main__':
    ; t$ r; o) E7 G3 N" w; B& ]0 A0 W9 s3 D
82.     head=Node('head')
    , b) M- O9 k. W8 d. Y
83.     link=List(head)
    
84.     for i in range(10):
    
85.         node=Node(i)
    
86.         link.append(node)
    
87.     print(link.print_list(head))
    1 o5 Y4 @. F1 c! p
88.     print(link.print_list(link.reverse(head)))

复制代码