题目描述
输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。
吐槽
本来想用递归实现,但是大脑卡壳,没有想到合适的递归策略,潜意识里还是把两个链表当成两个数组来看待,写出了非递归版本的代码。写完后回看自己写的代码,逻辑不够一目了然,中间变量过多,代码过长,一定不是好代码。上网查阅,发现一个如此美妙的递归版本,哇,写的好美啊!!!看来我对递归的了解和灵活应用还不够啊,至少在链表上还不够啊!!!
解题思路
思路1(非递归,Low)
找到两个链表中头节点值相对更小的链表,将其作为主链表,第二个链表中的元素则不断加入到主链表中。具体策略是:主链表定义两个指针,指向两个相邻的元素。当第二个链表中的元素值小于主链表中第二个指针时,将第二个链表的当前元素插入到主链表两个指针指向的元素中间,并调整指针指向。
Python代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
def Merge( self , pHead1, pHead2):
if not pHead1:
return pHead2
if not pHead2:
return pHead1
mainHead = pHead1 if pHead1.val < = pHead2.val else pHead2
secHead = pHead2 if mainHead = = pHead1 else pHead1
mergeHead = mainHead
mainNext = mainHead. next
while mainNext and secHead:
if secHead.val < = mainNext.val:
mainHead. next = secHead
secHead = secHead. next
mainHead. next . next = mainNext
mainHead = mainHead. next
else :
mainHead = mainNext
mainNext = mainNext. next
if not mainNext:
mainHead. next = secHead
return mergeHead
|
思路2(递归版本,Better)
网上找到的Java版本,思路如此清晰,以至于用任何额外的文字描述都显得多余。我用Python重现了思路,代码如下。哎,美妙的代码如此的赏心悦目,流连忘返啊…
1
2
3
4
5
6
7
8
9
10
11
|
def Merge( self , pHead1, pHead2):
if not pHead1:
return pHead2
if not pHead2:
return pHead1
if pHead1.val < = pHead2.val:
pHead1. next = self .Merge(pHead1. next , pHead2)
return pHead1
else :
pHead2. next = self .Merge(pHead1, pHead2. next )
return pHead2
|
最后给出包含测试部分的全部代码:
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
31
32
33
34
|
class Solution:
def Merge( self , pHead1, pHead2):
if not pHead1:
return pHead2
if not pHead2:
return pHead1
if pHead1.val < = pHead2.val:
pHead1. next = self .Merge(pHead1. next , pHead2)
return pHead1
else :
pHead2. next = self .Merge(pHead1, pHead2. next )
return pHead2
def getNewChart( self , list ):
if list :
node = ListNode( list .pop( 0 ))
node. next = self .getNewChart( list )
return node
class ListNode:
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)
while final:
print (final.val, end = " " )
final = final. next
|
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持服务器之家。
原文链接:https://blog.csdn.net/u010005281/article/details/79887949