leetcode 链接：合并两个有序链表

题目

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

示例：

  1. 输入：l1 = [1,2,4], l2 = [1,3,4]
  2. 输出：[1,1,2,3,4,4]
输入：l1 = [], l2 = []
输出：[]

输入：l1 = [], l2 = [0]
输出：[0]

解答 & 代码

使用双指针同时遍历两个链表，哪个指针指向的节点值更小，就先插入该节点，该指针前进一步
最后哪个链表不为空，再链上该链表的剩余部分

/**
 * 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* l1, ListNode* l2) {
        ListNode* dummyHead = new ListNode(-1);

        ListNode* cur1 = l1;
        ListNode* cur2 = l2;
        ListNode* pre = dummyHead;
        while(cur1 != nullptr && cur2!= nullptr)
        {
            if(cur1->val <= cur2->val)
            {
                pre->next = cur1;
                pre = cur1;
                cur1 = cur1->next;
            }
            else
            {
                pre->next = cur2;
                pre = cur2;
                cur2 = cur2->next;
            }
        }
        pre->next = (cur1 != nullptr) ? cur1 : cur2;
        return dummyHead->next; 
    }
};

执行结果：

执行结果：通过

执行用时：12 ms, 在所有 C++ 提交中击败了 48.56% 的用户
内存消耗：14.4 MB, 在所有 C++ 提交中击败了 60.35% 的用户