Python数据结构之翻转链表
翻转一个链表
样例:给出一个链表1->2->3->null,这个翻转后的链表为3->2->1->null
一种比较简单的方法是用“摘除法”。就是先新建一个空节点,然后遍历整个链表,依次令遍历到的节点指向新建链表的头节点。
那样例来说,步骤是这样的:
1.新建空节点:None
2.1->None
3.2->1->None
4.3->2->1->None
代码就非常简单了:
""" DefinitionofListNode classListNode(object): def__init__(self,val,next=None): self.val=val self.next=next """ classSolution: """ @paramhead:Thefirstnodeofthelinkedlist. @return:Youshouldreturntheheadofthereversedlinkedlist. Reverseitin-place. """ defreverse(self,head): temp=None whilehead: cur=head.next head.next=temp temp=head head=cur returntemp #writeyourcodehere
当然,还有一种稍微难度大一点的解法。我们可以对链表中节点依次摘链和链接的方法写出原地翻转的代码:
""" DefinitionofListNode classListNode(object): def__init__(self,val,next=None): self.val=val self.next=next """ classSolution: """ @paramhead:Thefirstnodeofthelinkedlist. @return:Youshouldreturntheheadofthereversedlinkedlist. Reverseitin-place. """ defreverse(self,head): ifheadisNone: returnhead dummy=ListNode(-1) dummy.next=head pre,cur=head,head.next whilecur: temp=cur #把摘链的地方连起来 pre.next=cur.next cur=pre.next temp.next=dummy.next dummy.next=temp returndummy.next #writeyourcodehere
需要注意的是,做摘链的时候,不要忘了把摘除的地方再连起来
感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!