单链表反转python实现代码示例

时间:2021-05-22

单链表的反转可以使用循环,也可以使用递归的方式

1.循环反转单链表

循环的方法中,使用pre指向前一个结点,cur指向当前结点,每次把cur->next指向pre即可。

代码:

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;

运行结果同上。

总结

以上就是本文关于单链表反转python实现代码示例的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题,如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!

声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。

相关文章