LeetCode 21：合并两个有序链表

题目描述

题目链接：https://leetcode-cn.com/problems/merge-two-sorted-lists/description/

题目与思路分析

目标分析：

1. 将两个升序链表合并为一个升序链表
2. 返回新链表的头指针
3. 新链表中的结点由已有两链表中的节点组成
4. 提高要求：时间复杂度为 O(n)，空间复杂度为 O(1)

思路一：尾插

思路：创建一个新的空链表 newHead，同时逐个遍历两个链表的结点，将 val 较小的节点尾插到新链表中。

操作：

• 注意对空链表的处理，两个链表可能都为空，也可能任意一个为空。
• 遍历：循环继续的条件为 curNode1 && curNode2，只要有一个链表结束，结束即可，将未遍历完的链表直接整体尾插到新链表中。
  • curNode1 和 curNode2：分别用于遍历链表一和链表二
  • tailNode：尾结点，方便尾插时找尾
• curNode1->val <= curNode2->val 时，说明：curNode1 需要被尾插到新链表。
  • 第一次尾插时 (if(newHead == nullptr) 需要特殊处理：
    • tailNode = newHead = curNode;
    • curNode = curNode->next;
  • 其余结点的尾插，常规化处理：
    • tailNode->next = curNode;
    • tailNode = tailNode->next;
  • 插入完后：curNode = curNode->next;
• curNode1->val > curNode2->val 时和上面是一样的逻辑。
• 循环结束后，检查哪个链表未遍历完全，直接整体尾插到新链表中。

// 循环结束后，可能链表还有剩余元素
if(curNode1) tailNode->next = curNode1;
(curNode2) tailNode->next = curNode2;