題目描述：
將兩個(gè)有序鏈表合并為一個(gè)新的有序鏈表并返回尊惰。新鏈表是通過(guò)拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的温数。
示例：
- 輸入：1->2->4, 1->3->4
- 輸出：1->1->2->3->4->4
我的方法：
這個(gè)題目比較簡(jiǎn)單，解法如下：
- 兩個(gè)指針?lè)謩e指向兩個(gè)鏈表的頭部搬味。
- 比較對(duì)應(yīng)位置的數(shù)字大小，記錄較小的字符，對(duì)應(yīng)的指針移到下一位椿猎。
- 直到兩個(gè)鏈表都遍歷完惶岭。
效果還不錯(cuò)：執(zhí)行用時(shí) : 32 ms, 在Merge Two Sorted Lists的Python提交中擊敗了99.60% 的用戶。內(nèi)存消耗 : 10.8 MB, 在Merge Two Sorted Lists的Python提交中擊敗了0.57% 的用戶犯眠。
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
ans=ListNode(0)
head=ans
while l1 and l2:
if l1.val <= l2.val:
ans.next=l1
ans=ans.next # 注意：ans也要移動(dòng)
l1=l1.next
else:
ans.next=l2
ans=ans.next # 注意：ans也要移動(dòng)
l2=l2.next
ans.next=l1 if l1 else l2
return head.next
別人的方法：
也有人用遞歸的方法按灶，雖然速度略慢，但思路依然可以借鑒筐咧。處理步驟如下：
- mergeTwoLists(self,l1,l2)的主要功能鸯旁，是將兩個(gè)有序鏈表合成一個(gè)有序鏈表。遞歸只需要關(guān)注移動(dòng)和終止條件兩個(gè)問(wèn)題量蕊。
- 終止條件是l1為空或者l2為空铺罢。如果l1為空，則返回l2残炮；如果l2為空韭赘，則返回l1。
- 遞歸事實(shí)上是問(wèn)題拆解為子問(wèn)題的過(guò)程势就，本題是將merge(l1,l2)轉(zhuǎn)化為merge(l1.next,l2)或者merge(l1,l2.next)泉瞻。通過(guò)這種轉(zhuǎn)化，實(shí)現(xiàn)鏈表的移動(dòng)蛋勺。
- 最終返回head.next瓦灶。
最終運(yùn)行效率一般，遞歸的效率一般都不是最高的抱完。執(zhí)行用時(shí) : 36 ms, 在Merge Two Sorted Lists的Python提交中擊敗了50.40% 的用戶贼陶。內(nèi)存消耗 : 10.9 MB, 在Merge Two Sorted Lists的Python提交中擊敗了0.57% 的用戶。
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
# 終止條件
if not l1: return l2
if not l2: return l1
head = ListNode(0)
# 當(dāng)l1.val<l2.val巧娱，則l1向后移動(dòng)一位
if l1.val < l2.val:
l1.next = self.mergeTwoLists(l1.next, l2)
head.next = l1
# 否則碉怔，l2向后移動(dòng)一位
else:
l2.next = self.mergeTwoLists(l1, l2.next)
head.next = l2
return head.next
