21. 合并两个有序链表
难度简单1527
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 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
均按 非递减顺序 排列
1.本题原链用不到了,所以直接可以用l1,l2来迭代
2.因为p1 p2任意为空循环就停了,所以不用p1p2判空了
3.因为是链表,所以不需要循环来进行新链的增添
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* p1 = l1;
ListNode* p2 = l2;
ListNode* newhead = new ListNode(0, l1);
ListNode* ans = newhead;
while(p1 != nullptr && p2 != nullptr){
if(p1 && p2 && p1->val <= p2->val){
newhead->next = new ListNode(p1->val);
p1 = p1->next;
newhead = newhead->next;
}else if(p1 && p2 && p1->val > p2->val){
newhead->next = new ListNode(p2->val);
p2 = p2->next;
newhead = newhead->next;
}
}
while(p1 != nullptr){
newhead->next = new ListNode(p1->val);
p1 = p1->next;
}
while(p2 != nullptr){
newhead->next = new ListNode(p2->val);
p2 = p2->next;
}
return ans->next;
}
};
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* newhead = new ListNode(-1);
ListNode* pre = newhead;
while(l1 != nullptr && l2 != nullptr){
if(l1->val <= l2->val){
pre->next = new ListNode(l1->val);
l1 = l1->next;
}else{
pre->next = new ListNode(l2->val);
l2 = l2->next;
}
pre = pre->next;
}
pre->next = l1 == nullptr ? l2 : l1;
return newhead->next;
}
};