目录
题目链接：21. 合并两个有序链表 - 力扣（LeetCode）
题目描述
示例
提示：
解法一：比大小放入
Java写法：
运行时间以及复杂度
C++写法：
运行时间以及复杂度
总结
题目链接：21. 合并两个有序链表 - 力扣（LeetCode）
注：下述题目描述和示例均来自力扣
题目描述
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = [] 输出：[]
示例 3：
输入：l1 = [], l2 = [0] 输出：[0]
提示：
- 两个链表的节点数目范围是
[0, 50] -100 <= Node.val <= 100l1和l2均按 非递减顺序 排列
解法一：比大小放入
- 初始化哨兵节点：
- 创建一个哨兵节点（dummy node），其
next指针指向null。这个哨兵节点将作为新链表的临时头部，这样做的好处是可以方便地在链表头部添加元素，而不需要特殊处理头节点为空的情况。
- 创建一个哨兵节点（dummy node），其
- 双指针迭代：
- 使用两个指针
list1和list2分别指向两个待合并链表的头部。 - 遍历这两个链表，直到其中一个链表被完全遍历（即其指针为
null）。 - 在每次迭代中，比较
list1和list2当前指向的节点的值：- 如果
list1的值较小或等于list2的值（由于题目中可能有重复元素，所以这里使用了小于等于），则将list1的当前节点连接到新链表的末尾（即哨兵节点的next指向的节点之后），并将list1的指针向后移动一位。 - 否则，将
list2的当前节点连接到新链表的末尾，并将list2的指针向后移动一位。
- 如果
- 同时，更新新链表的末尾指针（即
current指针），使其指向新添加的节点。
- 使用两个指针
- 处理剩余链表：
- 当其中一个链表被完全遍历后，如果另一个链表还有剩余节点（即其指针不为
null），则将这个剩余链表直接连接到新链表的末尾。 - 这是因为剩余的链表已经是有序的，所以可以直接添加而不需要进一步排序或比较。
- 当其中一个链表被完全遍历后，如果另一个链表还有剩余节点（即其指针不为
- 返回合并后的链表：
- 遍历结束后，新链表的头部就是哨兵节点的
next指针所指向的节点（因为哨兵节点只是为了方便操作而创建的，并不属于实际的合并结果）。 - 所以，返回哨兵节点的
next指针即可得到合并后的有序链表。
- 遍历结束后，新链表的头部就是哨兵节点的
Java写法：
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { // 创建一个哨兵节点，方便处理头节点 ListNode sentinel = new ListNode(0); ListNode current = sentinel; while (list1 != null && list2 != null) { if (list1.val < list2.val) { current.next = list1; list1 = list1.next; } else { current.next = list2; list2 = list2.next; } current = current.next; } // 如果list1或list2还有剩余节点，直接连接到结果链表的末尾 if (list1 != null) { current.next = list1; } if (list2 != null) { current.next = list2; } // 返回哨兵节点的下一个节点，即合并后的链表头节点 return sentinel.next; }
}运行时间以及复杂度
C++写法：
/** * 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* list1, ListNode* list2) { // 创建一个哨兵节点 ListNode* sentinel = new ListNode(0); ListNode* current = sentinel; // 使用双指针迭代合并两个链表 while (list1 != nullptr && list2 != nullptr) { if (list1->val < list2->val) { current->next = list1; list1 = list1->next; } else { current->next = list2; list2 = list2->next; } current = current->next; } // 处理剩余链表 if (list1 != nullptr) { current->next = list1; } if (list2 != nullptr) { current->next = list2; } // 返回合并后的链表头节点（哨兵节点的下一个节点） ListNode* mergedHead = sentinel->next; // 释放哨兵节点内存（可选，如果后续不再使用哨兵节点） delete sentinel; // 注意：在实际应用中，可能需要保留哨兵节点以简化链表操作 // 但由于哨兵节点在函数返回后可能无法再被访问，因此通常不会在这里删除它 // 除非你确定合并后的链表将使用新的头节点进行管理，并且哨兵节点不再需要 // 由于通常哨兵节点是为了方便链表操作而引入的，并且会在函数外部进行管理， // 因此这里我们不会删除哨兵节点，而是直接返回它指向的下一个节点作为合并后的链表头 return mergedHead; // 注意：上面的delete sentinel;在实际情况下通常是不应该执行的， // 因为哨兵节点是在函数内部创建的，并且其内存管理应该由调用者负责。 // 在这个例子中，我们直接返回了mergedHead，并没有删除哨兵节点。 }
}; // 注意：在实际使用中，通常不会删除哨兵节点，因为它只是作为一个辅助节点来帮助我们构建新链表。
// 调用者应该负责管理哨兵节点（尽管在这个特定的例子中，哨兵节点并没有被直接返回给调用者）。
// 但是，由于哨兵节点的`next`指针指向了合并后的链表头节点，我们可以安全地返回`mergedHead`而不用担心哨兵节点的内存泄漏。运行时间以及复杂度
总结
说点注意事项吧。
- 内存管理：在C++中，如果链表节点是动态分配的（如使用
new关键字），则需要注意内存泄漏的问题。然而，在这个特定的例子中，我们并没有直接返回哨兵节点，而是返回了哨兵节点的下一个节点作为合并后的链表头。因此，哨兵节点的内存管理应由调用者负责，但在函数内部通常不会删除它，因为哨兵节点只是作为辅助节点使用。 - 链表头节点：合并后的链表头节点是哨兵节点的下一个节点，它在新链表中是第一个真正的数据节点。
- 链表遍历：在迭代过程中，我们实际上是在遍历两个链表，并通过比较来构建新的链表。当其中一个链表被完全遍历后，我们只需将另一个链表的剩余部分连接到新链表的末尾即可。
- 链表结构：合并后的链表仍然保持升序排列，且其节点值来自原始的两个链表。
