python实现合并两个排序的链表
剑指offer:合并两个排序的链表,Python实现
题目描述
输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。
吐槽
本来想用递归实现,但是大脑卡壳,没有想到合适的递归策略,潜意识里还是把两个链表当成两个数组来看待,写出了非递归版本的代码。写完后回看自己写的代码,逻辑不够一目了然,中间变量过多,代码过长,一定不是好代码。上网查阅,发现一个如此美妙的递归版本,哇,写的好美啊!!!看来我对递归的了解和灵活应用还不够啊,至少在链表上还不够啊!!!
解题思路
思路1(非递归,Low)
找到两个链表中头节点值相对更小的链表,将其作为主链表,第二个链表中的元素则不断加入到主链表中。具体策略是:主链表定义两个指针,指向两个相邻的元素。当第二个链表中的元素值小于主链表中第二个指针时,将第二个链表的当前元素插入到主链表两个指针指向的元素中间,并调整指针指向。
Python代码
defMerge(self,pHead1,pHead2): ifnotpHead1: returnpHead2 ifnotpHead2: returnpHead1 mainHead=pHead1ifpHead1.val<=pHead2.valelsepHead2 secHead=pHead2ifmainHead==pHead1elsepHead1 mergeHead=mainHead mainNext=mainHead.next whilemainNextandsecHead: ifsecHead.val<=mainNext.val: mainHead.next=secHead secHead=secHead.next mainHead.next.next=mainNext mainHead=mainHead.next else: mainHead=mainNext mainNext=mainNext.next ifnotmainNext: mainHead.next=secHead returnmergeHead
思路2(递归版本,Better)
网上找到的Java版本,思路如此清晰,以至于用任何额外的文字描述都显得多余。我用Python重现了思路,代码如下。哎,美妙的代码如此的赏心悦目,流连忘返啊…
defMerge(self,pHead1,pHead2): ifnotpHead1: returnpHead2 ifnotpHead2: returnpHead1 ifpHead1.val<=pHead2.val: pHead1.next=self.Merge(pHead1.next,pHead2) returnpHead1 else: pHead2.next=self.Merge(pHead1,pHead2.next) returnpHead2
最后给出包含测试部分的全部代码:
classSolution: defMerge(self,pHead1,pHead2): ifnotpHead1: returnpHead2 ifnotpHead2: returnpHead1 ifpHead1.val<=pHead2.val: pHead1.next=self.Merge(pHead1.next,pHead2) returnpHead1 else: pHead2.next=self.Merge(pHead1,pHead2.next) returnpHead2 defgetNewChart(self,list): iflist: node=ListNode(list.pop(0)) node.next=self.getNewChart(list) returnnode classListNode: def__init__(self,x): self.val=x self.next=None if__name__=='__main__': list1=[1,3,5] list2=[0,1,4] testList1=Solution().getNewChart(list1) testList2=Solution().getNewChart(list2) final=Solution().Merge(testList1,testList2) whilefinal: print(final.val,end="") final=final.next
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持毛票票。