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

admin

题目：反向输出一个链表。
- h8 L# S; F4 N5 ^7 o程序分析：无。

1. class Node:
   ( h4 Y( e- H2 \  t8 B
2. 
   
3.     def __init__(self, data):
   * J& u) Z) J8 W7 n
4.         self.data = data
   
5.         self.next = None
   7 h  [- C" _" ~% {( e; e4 i& O
6. 
   $ Z8 S$ g' h) n4 _: `/ r8 Q
7.     def get_data(self):
   
8.         return self.data
   
9. 
     r: P3 V+ w5 @( U
10. class List:
    
11. 
    
12.     def __init__(self, head):
    
13.         self.head = head
    
14. 
    
15.     def is_empty(self):
    
16.         return self.get_len() == 0
    
17. 
    5 L1 T2 g& \+ j0 k5 c. b& v
18.     def get_len(self):  
    
19.         length = 0
    * H" e. |; M) @  ^
20.         temp = self.head
    - N5 s2 B' d3 y  T
21.         while temp is not None:
    
22.             length += 1
    
23.             temp = temp.next
    6 J- U7 B" n& G, Q; x# W
24.         return length
    
25. 
    
26.     def append(self, node):
    
27.         temp = self.head
    
28.         while temp.next is not None:
    : z: j5 p0 ]( e! G7 S
29.             temp = temp.next
    , K! Q7 a- w' R
30.         temp.next = node
    
31. 
    
32.     def delete(self, index):
    
33.         if index < 1 or index > self.get_len():
    
34.             print("给定位置不合理")
    
35.             return
    
36.         if index == 1:
    
37.             self.head = self.head.next
    " z' ^8 R% ]# [1 d' c! A$ ]
38.             return
    
39.         temp = self.head
    ( d' F9 t# L( B, g( o
40.         cur_pos = 0
    
41.         while temp is not None:
    6 e) L, \# N+ y
42.             cur_pos += 1
    : L$ I, }/ U/ T+ E
43.             if cur_pos == index-1:
    
44.                 temp.next = temp.next.next
    4 I5 L- }# O: {" U  P
45.             temp = temp.next
    / H8 K; ?" V2 w$ ]& n
46. 
    
47.     def insert(self, pos, node):
    
48.         if pos < 1 or pos > self.get_len():
    
49.             print("插入结点位置不合理")
    2 N# I* Y0 A! A  N# z! ~' j
50.             return
    
51.         temp = self.head
    
52.         cur_pos = 0
    ( L$ T( l$ s6 n; }
53.         while temp is not Node:
    $ B5 v, L8 X8 p3 C1 P8 X' S1 [1 t
54.             cur_pos += 1
    
55.             if cur_pos == pos-1:
    - `! z5 k0 e, k7 G
56.                 node.next = temp.next
    % }6 _8 J% L4 _. d8 w9 z
57.                 temp.next =node
    8 Z+ n& T1 p( W) Y% P* A
58.                 break
    1 h* J) A2 H" C* S& y: O
59.             temp = temp.next
    
60. 
      L( U/ p" g# C  Z( m6 J
61.     def reverse(self, head):
    1 M" Z. I% r9 l2 D. f: Q! W
62.         if head is None and head.next is None:
    : Q1 i# i9 i& v! h: a! g1 T+ `
63.             return head
    9 L$ }- W  H$ ]  t
64.         pre = head
    
65.         cur = head.next
    8 G% M. q2 ]" H7 i7 K- D7 }
66.         while cur is not None:
    7 W6 o6 A9 Z; s" q) h/ p' [" ]3 R
67.             temp = cur.next
    , l/ T1 y/ v/ v4 R  h+ r
68.             cur.next = pre
    $ j2 q9 Y# q7 `# z
69.             pre = cur
    * C& D( ^# ~5 ?& ?2 j; a/ ~
70.             cur = temp
    
71.         head.next = None
    0 E. F) P% I& u
72.         return pre
    
73. 
    
74.     def print_list(self, head):
    ( N% L! a2 W0 G! N/ q
75.         init_data = []
    
76.         while head is not None:
    
77.             init_data.append(head.get_data())
    $ @2 U' p; x  ^+ \2 `. w
78.             head = head.next
    
79.         return init_data
    
80. 
    5 l- a, [8 s: Z; Y: x4 b+ o
81. if __name__=='__main__':
    
82.     head=Node('head')
    2 B8 f9 m. v# M4 ~8 ?% D
83.     link=List(head)
    
84.     for i in range(10):
    
85.         node=Node(i)
    
86.         link.append(node)
    0 b) V. V1 [0 d( _9 `8 Z
87.     print(link.print_list(head))
    7 [# d6 T4 h7 h: H3 E. |  Z
88.     print(link.print_list(link.reverse(head)))

复制代码