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

admin

题目：反向输出一个链表。
- D% @0 {5 Z$ k程序分析：无。
9 j, w- C5 [3 ~+ K( J

1. class Node:
   
2. 
   
3.     def __init__(self, data):
   . z* D! y  @$ H9 `
4.         self.data = data
   ' c1 o2 V: S  O& g' N  J2 q
5.         self.next = None
   
6. 
   
7.     def get_data(self):
   
8.         return self.data
   ! ]: K- o& `9 _, {0 C, \. \+ Z
9. 
   / H8 z& F3 s) w: Y& x2 c
10. class List:
    6 o" q5 [- _2 Z  ^. H3 W' R, S
11. 
    
12.     def __init__(self, head):
    3 _4 w, V  |9 d! A4 H% {6 i4 D1 l, `* L
13.         self.head = head
    1 D' ~. h/ c- y/ q+ }
14. 
    , t: J4 |( F" y7 M5 z
15.     def is_empty(self):
    
16.         return self.get_len() == 0
    6 \2 N' T% U: _( J
17. 
    9 G0 Y' D2 l) t" h5 S8 B
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
    
24.         return length
    3 q0 v: s/ n8 k( t3 U( F) [
25. 
    
26.     def append(self, node):
    
27.         temp = self.head
    
28.         while temp.next is not None:
    
29.             temp = temp.next
    
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:
    9 ]0 }" Z2 u/ f, s% X
37.             self.head = self.head.next
    
38.             return
    
39.         temp = self.head
    
40.         cur_pos = 0
    ' P: K( @& S, @# L* D
41.         while temp is not None:
    3 N9 _* R$ D0 b  T3 o  `
42.             cur_pos += 1
    ! F# W+ A* M3 S7 l, A% r
43.             if cur_pos == index-1:
    
44.                 temp.next = temp.next.next
    1 W' l" Q2 ]4 O
45.             temp = temp.next
    
46. 
    " S+ ?. z( @( i( D+ j# C
47.     def insert(self, pos, node):
    1 z, M- |2 H; M. b) I( f# v5 [8 |
48.         if pos < 1 or pos > self.get_len():
    3 {" P2 F; h& s3 s) d* t6 @$ F
49.             print("插入结点位置不合理")
    # d9 W: S! I, f& I
50.             return
    
51.         temp = self.head
    
52.         cur_pos = 0
    
53.         while temp is not Node:
    ' \+ @$ \0 o5 v2 c
54.             cur_pos += 1
    
55.             if cur_pos == pos-1:
    
56.                 node.next = temp.next
    
57.                 temp.next =node
    
58.                 break
    0 a3 v5 y) L) a. g0 q
59.             temp = temp.next
    
60. 
    
61.     def reverse(self, head):
    % C5 c/ u( z  `: {' h* q7 W
62.         if head is None and head.next is None:
    ' P1 W( s8 M- [/ e
63.             return head
    4 F& h% n4 d9 ~6 w* \# K# U
64.         pre = head
    ; v- g1 t# W; T  t" g
65.         cur = head.next
    7 u% C# N6 f7 W1 _' {+ h7 G0 r$ j9 O
66.         while cur is not None:
    % Z; b- F7 W5 I6 A
67.             temp = cur.next
    4 c9 k  M/ v2 o* x" W! q! a
68.             cur.next = pre
    0 i, j% c4 ?* \$ b
69.             pre = cur
    % L  H% S1 }+ _* S* e
70.             cur = temp
    4 |! a6 U8 X2 P2 s' c
71.         head.next = None
    
72.         return pre
    
73. 
    
74.     def print_list(self, head):
    
75.         init_data = []
    0 Y/ {6 @# _1 V  w
76.         while head is not None:
    
77.             init_data.append(head.get_data())
    
78.             head = head.next
    
79.         return init_data
    6 c) @3 x. F$ ]7 u
80. 
    
81. if __name__=='__main__':
    
82.     head=Node('head')
    ( n; z7 v3 }  J$ M$ n& t
83.     link=List(head)
    
84.     for i in range(10):
    ' ~$ V: Z$ h" k. v! E
85.         node=Node(i)
    " z6 s5 N% ?' g% h8 ~' ?
86.         link.append(node)
    ' e, M7 O- _+ K
87.     print(link.print_list(head))
    ' X; e$ ^5 M- ~; L
88.     print(link.print_list(link.reverse(head)))

复制代码