單鏈表反轉python實現代碼示例

2020-01-04 15:54:50

字體：大中小

來源：轉載

供稿：網友

單鏈表的反轉可以使用循環，也可以使用遞歸的方式

1.循環反轉單鏈表

循環的方法中，使用pre指向前一個結點，cur指向當前結點，每次把cur->next指向pre即可。

單鏈表反轉,python,實現單鏈表,遞歸實現單鏈表反轉,單鏈表排序,單鏈表逆置

代碼：

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.遞歸實現單鏈表反轉

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;

運行結果同上。