网站建设与开发的软件,wordpress 大前端,wdcp和wordpress,查淘宝关键词排名软件21. 合并两个有序链表 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1#xff1a; 输入#xff1a;l1 [1,2,4], l2 [1,3,4] 输出#xff1a;[1,1,2,3,4,4] 示例 2#xff1a; 输入#xff1a;l1 [], l2 [] …21. 合并两个有序链表 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1 输入l1 [1,2,4], l2 [1,3,4] 输出[1,1,2,3,4,4] 示例 2 输入l1 [], l2 [] 输出[] 示例 3 输入l1 [], l2 [0] 输出[0] 提示 两个链表的节点数目范围是 [0, 50] -100 Node.val 100 l1 和 l2 均按 非递减顺序 排列 思路
两种思路
在已有的链表 l1 上插入 l2插入排序思想重新从空节点开始构建链表
在已有的链表 l1 上插入 l2插入排序思想
为什么会想到插入排序插入排序的过程中前半部分是有序的后半部分的无序元素逐个插入前面的有序部分这道题可以把 l1 视作排序完成的前半部分l2 视作后半部分插入前半部分在这种做法下其实相当于把两个序列拼接起来后再排序需要一个当前遍历到的 l1 元素的前一个元素的指针 preL1便于插入 l2 元素l2 元素在插入前应保存下一个要比较的 l2 元素 l2-next否则无法接着遍历 ListNode* temp l2-next;使用假头 dummyHead确保可以插入 l1 的第一个元素前面遍历 l1 元素时使用 preL1 l1; l1 l1-next;
class Solution {
public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {//排除有空链表的情况if(!l1) return l2;if(!l2) return l1;ListNode* dummyHead1 new ListNode(-101);dummyHead1-next l1;ListNode* preL1 dummyHead1;while(l1 l2){while(l1 l2-val l1-val){preL1 l1;l1 l1-next;}//此时l1为空或者l2指向的节点比l1指向的节点小比l1节点的前一个节点大if(!l1){//处理l1为空的情况preL1-next l2;return dummyHead1-next;}//处理l2指向的节点比l1指向的节点小比l1节点的前一个节点大的情况while(l2 l2-val preL1-val l2-val l1-val){preL1-next l2;ListNode* temp l2-next;l2-next l1;preL1 l2;l2 temp;} }return dummyHead1-next;}
};重新从空节点开始构建链表
首先定义一个假头然后比较 l1 和 l2 的元素小的就添加在新链表的后面不断循环最后当有一个链表为空就把剩下的都接在新链表的后面即可
class Solution {
public:ListNode* trainningPlan(ListNode* l1, ListNode* l2) {ListNode* dum new ListNode(0);ListNode* cur dum;while(l1 l2){if(l1-val l2-val){cur-next l1;cur l1;l1 l1-next;}else{cur-next l2;cur l2;l2 l2-next;}}if(!l1) cur-next l2;if(!l2) cur-next l1;return dum-next;}
};
