LeetCode 21.合并两个有序链表

题目
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
LeetCode 21.合并两个有序链表

分析
定义result储存结果,将两个链表各自遍历一遍,每次各拿出一个结点比较,把较小的连接在result后面,直到至少有一个链表元素全用完,此时,将另一个链表剩余部分直接连接在当前结果后面。

图解
LeetCode 21.合并两个有序链表
LeetCode 21.合并两个有序链表
LeetCode 21.合并两个有序链表

代码

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* result = new ListNode(-1);
        ListNode* cur1 = l1;
        ListNode* cur2 = l2;
        ListNode* cur = result;
        while (cur1 != nullptr && cur2 != nullptr) {
            if (cur1->val < cur2->val) {
                cur->next = cur1;
                cur1 = cur1->next;
            }
            else {
                cur->next = cur2;
                cur2 = cur2->next;
            }
            cur = cur->next;
        }
        if (cur1 == nullptr) cur->next = cur2;
        if (cur2 == nullptr) cur->next = cur1;
        return result->next;
    }
};
上一篇:链表相交问题


下一篇:260. 只出现一次的数字 III --LeetCode每日一题打卡