Diffculty
medium
Language
Explain
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
Example
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
Solve
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if not l1:
return l2
if not l2:
return l1
if l1.val < l2.val:
l1.next = self.mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = self.mergeTwoLists(l2.next, l1)
return l2
Performace
Runtime: 40 ms, faster than 88.50% of Python3 online submissions for Merge Two Sorted Lists.
Memory Usage: 13.9 MB, less than 6.61% of Python3 online submissions for Merge Two Sorted Lists.
性能一般，但是思路很赞，非常简洁得用递归解决了问题