Leetcode 21 Merge Two Sorted Lists"/>
Leetcode 21 Merge Two Sorted Lists
Leetcode 21 Merge Two Sorted Lists
题目描述
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
来源:力扣(LeetCode)
链接:
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路解析
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = Noneclass Solution:def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:if l1 is None:return l2elif l2 is None:return l1result = ListNode(0) # 哑结点result_temp = resultwhile l1 and l2:if l1.val <= l2.val:result_temp.next = ListNode(l1.val)result_temp = result_temp.nextl1 = l1.nextelse:result_temp.next = ListNode(l2.val)result_temp = result_temp.nextl2 = l2.nextif l1 is None:result_temp.next = l2else:result_temp.next = l1return result.next
- 递归写法
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = Noneclass Solution:def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:if l1 is None:return l2elif l2 is None:return l1if l1.val <= l2.val:l1.next = self.mergeTwoLists(l1.next, l2)return l1else:l2.next = self.mergeTwoLists(l2.next, l1)return l2
递归的代码要简洁得多,思路也很优美,但空间复杂度往往很高,现实中并不建议使用递归。
更多推荐
Leetcode 21 Merge Two Sorted Lists
发布评论