leetcode：21. 合并两个有序链表

题目

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

示例：
[简单] 21. 合并两个有序链表 - 图1

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

解答 & 代码

  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode() : val(0), next(nullptr) {}
  7.  *     ListNode(int x) : val(x), next(nullptr) {}
  8.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
  9.  * };
  10.  */
  11. class Solution {
  12. public:
  13.     ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
  14.         if(l1== nullptr && l2 == nullptr)
  15.             return nullptr;
  17.         ListNode* dummyHead = new ListNode();        // 虚拟头节点
  18.         ListNode* pre = dummyHead;    // 指向（合并后）新链表的尾节点
  19.         ListNode* cur1 = l1;                // 指向 l1 链表当前节点的指针
  20.         ListNode* cur2 = l2;                // 指向 l2 链表当前节点的指针
  21.           // 使用 cur1、cur2 双指针同时遍历两个链表，将两者中值较小的节点插入新链表的尾部
  22.         while(cur1 != nullptr && cur2 != nullptr)
  23.         {
  24.             if(cur1->val <= cur2->val)
  25.             {
  26.                 pre->next = cur1;
  27.                 cur1 = cur1->next;
  28.             }
  29.             else
  30.             {
  31.                 pre->next = cur2;
  32.                 cur2 = cur2->next;
  33.             }
  34.             pre = pre->next;
  35.         }
  36.           // 最后如果 l1 链表还没遍历完，直接将剩余部分接到新链表尾部
  37.         if(cur1 != nullptr)
  38.             pre->next = cur1;
  39.           // 最后如果 l2 链表还没遍历完，直接将剩余部分接到新链表尾部
  40.         else if(cur2 != nullptr)
  41.             pre->next = cur2;
  42.         return dummyHead->next;
  43.     }
  44. };

复杂度分析：设两个链表长度分别为 m、n

  • 时间复杂度 O(m + n)
  • 空间复杂度 O(1)

执行结果：

  1. 执行结果：通过
  3. 执行用时：12 ms, 在所有 C++ 提交中击败了 13.54% 的用户
  4. 内存消耗：14.5 MB, 在所有 C++ 提交中击败了 21.95% 的用户