日野弥生：勉強しよう
LeetCode 21 - 合并两个有序链表
发表于2025年01月27日
合并两个有序链表前，先确定插入方链表和被插入方链表，以链表头的值大小裁定。
需要注意插入行为满足的条件是插入方当前指针不为空，且插入方当前值比被插入方当前值大，且比被插入方的指针的下一个值小。或者被插入方下一个指针为空（即被插入方当前为最后一个结点）。
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
/* 任一链表为空，都无需合并 */
if(!list1) return list2;
if(!list2) return list1;
/* 确认把链表1插入链表2 */
if(list1->val < list2->val)
std::swap(list1, list2);
ListNode *insertCurr = list1, *beInsertedCurr = list2;
while(beInsertedCurr && insertCurr)
{
ListNode *insertNext = insertCurr->next;
/* 发生插入行为需要满足的条件： */
if(insertCurr && insertCurr->val >= beInsertedCurr->val && (!beInsertedCurr->next ||
insertCurr->val < beInsertedCurr->next->val))
{
ListNode *beInsertedNext = beInsertedCurr->next;
beInsertedCurr->next = insertCurr;
insertCurr->next = beInsertedNext;
insertCurr = insertNext;
}
beInsertedCurr = beInsertedCurr->next;
}
return list2;
}
};