21_合并两个有序链表
【问题描述】
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例一：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例二：
输入：l1 = [], l2 = []
输出：[]
示例三：
输入：l1 = [], l2 = [0]
输出：[0]
提示：
- 两个链表的节点数目范围是
[0, 50] -100 <= Node.val <= 100l1和l2均按 非递减顺序 排列
【算法设计思想】
- 在解决本题时，我们需要创建一个新的带有头结点的单链表（操作方便）用来做返回的结果，然后我们初始化一个指针指向这个名为prehead的结点用来便于我们进行相关的操作。
- 接下来，我们初始化p1和p2两个指针变量来分别指向我们要进行操作的两个单链表，当不为空时，我们判断其所指向元素的大小，加入到我们的结果中。
- 最后，我们看下是否有剩余，然后直接把剩余的所有元素加入到我们的结果链表中即可。
注意：在这里我们要返回prehead -> 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* prehead = new ListNode(-1);
// prev指针用于遍历和构建合并后的链表
ListNode* prev = prehead;
// 两个指针分别指向两个链表的起始位置
ListNode* p1 = list1;
ListNode* p2 = list2;
// 遍历两个链表，直到其中一个链表结束
while (p1 != nullptr && p2 != nullptr) {
// 比较 p1 和 p2 所指节点的值，将较小的节点连接到结果链表
if (p1->val > p2->val) {
prev->next = p2; // p2 较小，连接到结果链表
p2 = p2->next; // p2 向后移动
} else {
prev->next = p1; // p1 较小或相等，连接到结果链表
p1 = p1->next; // p1 向后移动
}
prev = prev->next; // prev 向后移动，继续构建结果链表
}
// 如果链表1还有剩余的节点，直接连接
if (p1 != nullptr) {
prev->next = p1;
}
// 如果链表2还有剩余的节点，直接连接
if (p2 != nullptr) {
prev->next = p2;
}
// 返回合并后的链表头节点（跳过虚拟头节点）
return prehead->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 {
/**
* 合并两个升序链表，并返回合并后的新链表。
* @param list1 第一个有序链表
* @param list2 第二个有序链表
* @return 合并后的有序链表
*/
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
// 创建一个虚拟头节点，用于简化链表的连接操作
ListNode prehead = new ListNode(-1);
// prev 指针用于构建合并后的链表
ListNode prev = prehead;
// 遍历两个链表，直到其中一个链表遍历结束
while (list1 != null && list2 != null) {
// 如果 list1 的当前节点的值大于等于 list2 的当前节点
if (list1.val >= list2.val) {
// 将 list2 的当前节点连接到结果链表
prev.next = list2;
// 移动 list2 指针到下一个节点
list2 = list2.next;
} else {
// 否则，将 list1 的当前节点连接到结果链表
prev.next = list1;
// 移动 list1 指针到下一个节点
list1 = list1.next;
}
// 移动 prev 指针到下一个位置，准备连接下一个节点
prev = prev.next;
}
// 如果 list1 还有剩余节点，直接将其连接到结果链表
if (list1 != null) {
prev.next = list1;
}
// 如果 list2 还有剩余节点，直接将其连接到结果链表
if (list2 != null) {
prev.next = list2;
}
// 返回合并后的链表头节点，跳过虚拟头节点
return prehead.next;
}
}
Python：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
# 创建一个虚拟头节点，用于简化链表的合并操作
prehead = ListNode(-1)
# prev 指针用于构建合并后的链表，初始指向虚拟头节点
prev = prehead
# 遍历两个链表，直到其中一个链表遍历完毕
while list1 is not None and list2 is not None:
# 比较 list1 和 list2 当前节点的值
if list1.val >= list2.val:
# 如果 list2 的值较小，将 list2 的节点连接到合并链表
prev.next = list2
# 移动 list2 指针到下一个节点
list2 = list2.next
else:
# 如果 list1 的值较小，将 list1 的节点连接到合并链表
prev.next = list1
# 移动 list1 指针到下一个节点
list1 = list1.next
# 移动 prev 指针到下一个位置，准备连接下一个节点
prev = prev.next
# 如果 list1 链表还有剩余节点，直接将其连接到合并链表
if list1 is not None:
prev.next = list1
# 如果 list2 链表还有剩余节点，直接将其连接到合并链表
if list2 is not None:
prev.next = list2
# 返回合并后的链表，跳过虚拟头节点
return prehead.next
C：
/**
* Definition for singly-linked list.
* 结构体定义一个单链表节点
* struct ListNode {
* int val; // 节点值
* struct ListNode *next; // 指向下一个节点的指针
* };
*/
// 合并两个已排序的链表
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
// 创建一个伪头节点，方便处理合并后的链表
struct ListNode* prehead = (struct ListNode*)malloc(sizeof(struct ListNode));
prehead -> next = NULL; // 初始化伪头节点的next为NULL
// prev用于追踪合并后链表的当前最后一个节点
struct ListNode* prev = prehead;
// 当两个链表都不为空时进行循环
while(list1 != NULL && list2 != NULL){
// 如果list2的当前节点值小于等于list1的当前节点值，则将list2的当前节点插入到结果链表中
if(list1 -> val >= list2 -> val){
prev -> next = list2;
// 移动list2的头指针到下一个节点
list2 = list2 -> next;
}
// 否则，将list1的当前节点插入到结果链表中
else{
prev -> next = list1;
// 移动list1的头指针到下一个节点
list1 = list1 -> next;
}
// 更新prev指向当前链表的最后一个节点
prev = prev -> next;
}
// 如果list1还有剩余节点，则直接连接到结果链表之后
if(list1 != NULL){
prev -> next = list1;
}
// 如果list2还有剩余节点，则直接连接到结果链表之后
if(list2 != NULL){
prev -> next = list2;
}
// 返回合并后的链表（从prehead的下一个节点开始）
return prehead -> next;
}