中卫企业管理培训网站,app开发公司怎么选择,WordPress主题Perimg,甘肃省建设社厅网站文章目录 Tag题目来源题目解读解题思路方法一#xff1a;递归方法二#xff1a;迭代 写在最后 Tag
【递归】【迭代】【链表】 题目来源
21. 合并两个有序链表 题目解读
合并两个有序链表。 解题思路
一种朴素的想法是将两个链表中的值存入到数组中#xff0c;然后对数组… 文章目录 Tag题目来源题目解读解题思路方法一递归方法二迭代 写在最后 Tag
【递归】【迭代】【链表】 题目来源
21. 合并两个有序链表 题目解读
合并两个有序链表。 解题思路
一种朴素的想法是将两个链表中的值存入到数组中然后对数组进行升序排序最后将排序好的数组还原回链表这是一种可行的思路但是没有充分利用题目已知的两个链表有序的条件大家可以自行尝试练习基础语法与建立链表节点的知识。
方法一递归
我们记两个链表的头节点分别为 l1 和 l2在合并两个链表的时候会遇到以下三种情况
l1 为空直接返回 l2l2 为空直接返回 l1;两节点都不为空那么又会分为两种情况: l1 节点值小于 l2 节点值那么 l1 节点将会是合并后的节点新的头节点剩下的部分是 l1-next 和 l2 合并的节点而合并 l1-next 和 l2 是合并 l1 和 l2 的子问题也可以使用 mergeTwoLists 函数来解答于是有 l1-next mergeTwoLists(l1-next, l2)并返回 l1同理l2 节点值小于 l1 节点值时有 l2-next mergeTwoLists(l1, l2-next)并返回 l1。 以上这种将问题转换为原问题的子问题的方法称为递归方法。递归方法是一种边调用边填充的方法。
实现代码
C
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {if (list1 nullptr) {return list2;}else if (list2 nullptr) {return list1;}else if (list1-val list2-val) {list1-next mergeTwoLists(list1-next, list2);return list1;}else {list2-next mergeTwoLists(list1, list2-next);return list2;}}
};python3
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]) - Optional[ListNode]:if l1 is None:return l2elif l2 is None:return l1elif l1.val l2.val:l1.next self.mergeTwoLists(l1.next,l2)return l1else:l2.next self.mergeTwoLists(l1, l2.next)return l2 复杂度分析
时间复杂度 O ( m n ) O(mn) O(mn) m m m 和 n n n 分别为两个链表的长度每个节点都是被递归调用一次。
空间复杂度 O ( m n ) O(mn) O(mn)每调用一次函数 mergeTwoLists 都需要消耗栈空间栈空间的大小取决于递归调用的深度。
方法二迭代
迭代的方法是一种相对容易理解的方法。为了方便实现我们定义一个哑节点 dummyListNode* dummy new ListNode(-1);最后只需要返回 dummy-next。
我们再定义一个节点 prev 用来指向当前值较小的节点初始 prev dummy我们迭代枚举两链表中的节点
prev 指向值较小的节点值较小的节点更新为下一个节点方便下一对节点的比较prev 更新为下一个节点为存放下一个更小的节点做准备如果有一个链表为空了直接退出迭代循环需要注意这时候两个链表中可能还有一个链表非空需要将剩下的非空部分接在 prev 后面。
以上就是本题的迭代方法。
实现代码
C
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode* dummy new ListNode(-1);ListNode* prev dummy;while(list1 list2){if(list1-val list2-val){prev-next list1;list1 list1-next;}else{prev-next list2;list2 list2-next;}prev prev-next;}prev-next list1 ? list1 : list2;return dummy-next;}
};python3
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]) - Optional[ListNode]:dummy ListNode(-1)prev dummywhile l1 and l2:if l1.val l2.val:prev.next l1l1 l1.nextelse:prev.next l2l2 l2.nextprev prev.nextprev.next l1 if l1 is not None else l2return dummy.next复杂度分析
时间复杂度 O ( m n ) O(mn) O(mn) m m m 和 n n n 分别为两个链表的长度每个节点都是被递归调用一次。
空间复杂度 O ( 1 ) O(1) O(1)。 写在最后
如果文章内容有任何错误或者您对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度方法欢迎评论区交流。
最后感谢您的阅读如果感到有所收获的话可以给博主点一个 哦。
