單鏈表的反轉可以使用循環，也可以使用遞歸的方式
1.循環反轉單鏈表
循環的方法中，使用pre指向前一個結點，cur指向當前結點，每次把cur->next指向pre即可。
代碼：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
class ListNode: def __init__(self,x): self.val=x; self.next=None; def nonrecurse(head): #循環的方法反轉鏈表 if head is None or head.next is None: return head; pre=None; cur=head; h=head; while cur: h=cur; tmp=cur.next; cur.next=pre; pre=cur; cur=tmp; return h; head=ListNode(1); #測試代碼 p1=ListNode(2); #建立鏈表1->2->3->4->None; p2=ListNode(3); p3=ListNode(4); head.next=p1; p1.next=p2; p2.next=p3; p=nonrecurse(head); #輸出鏈表 4->3->2->1->None while p: print p.val; p=p.next; |
結果：
4
3
2
1
>>>
2.遞歸實現單鏈表反轉
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
class ListNode: def __init__(self,x): self.val=x; self.next=None; def recurse(head,newhead): #遞歸，head為原鏈表的頭結點，newhead為反轉后鏈表的頭結點 if head is None: return ; if head.next is None: newhead=head; else : newhead=recurse(head.next,newhead); head.next.next=head; head.next=None; return newhead; head=ListNode(1); #測試代碼 p1=ListNode(2); # 建立鏈表1->2->3->4->None p2=ListNode(3); p3=ListNode(4); head.next=p1; p1.next=p2; p2.next=p3; newhead=None; p=recurse(head,newhead); #輸出鏈表4->3->2->1->None while p: print p.val; p=p.next; |
運行結果同上。
總結
以上就是本文關于單鏈表反轉python實現代碼示例的全部內容，希望對大家有所幫助。感興趣的朋友可以繼續參閱本站其他相關專題，如有不足之處，歡迎留言指出。感謝朋友們對本站的支持！
原文鏈接：http://blog.csdn.net/u011608357/article/details/36933337
