目录
题目
图解
方法一
方法二
代码(解析在注释中)
方法一
编辑方法二
题目
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 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 均按 非递减顺序 排列
图解
方法一
最终效果
方法二
这个方法就比上一个方法多了一个“哨兵”，也就是用malloc开辟的一个辅助空间
代码(解析在注释中)
方法一
/**
* 定义单链表结构体
* 结构体中包含整数值val以及指向下一个节点的指针next
*/
typedef struct ListNode ListNode;
struct ListNode {
int val;
struct ListNode *next;
};
/**
* 函数mergeTwoLists接收两个单链表（list1和list2）作为参数，
* 并返回合并后的新链表，新链表中的元素按升序排列。
*/
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
// 首先判断输入的两个链表是否为空，如果其中一个为空，则直接返回另一个非空链表
if (list1 == NULL) {
return list2;
}
if (list2 == NULL) {
return list1;
}
// 为了不对原链表进行修改，创建两个指针l1和l2分别指向list1和list2的头部
ListNode* l1 = list1;
ListNode* l2 = list2;
// 初始化新链表的头结点和尾结点为NULL
ListNode *Newhead, *Newtail;
Newhead = Newtail = NULL;
// 使用while循环遍历两个链表直到其中一个链表遍历完为止
while (l1 && l2) {
// 比较当前节点的值大小，将较小值的节点添加到新链表中
if (l1->val < l2->val) {
// 如果新链表还未添加过节点，则设置新链表的头结点和尾结点都为l1
if (Newhead == NULL) {
Newhead = Newtail = l1;
} else {
// 否则将尾结点的next指向l1，并更新尾结点为新添加的节点
Newtail->next = l1;
Newtail = Newtail->next;
}
// 移动l1指针至下一个节点
l1 = l1->next;
} else {
// 类似地处理l2的情况
if (Newhead == NULL) {
Newhead = Newtail = l2;
} else {
Newtail->next = l2;
Newtail = Newtail->next;
}
l2 = l2->next;
}
}
// 当某一个链表遍历完之后，将未遍历完的链表剩余部分连接到新链表的尾部
if (l1) {
Newtail->next = l1;
}
if (l2) {
Newtail->next = l2;
}
// 返回新链表的头结点
return Newhead;
}
方法二
/**
* 定义单链表结构体
* 结构体中包含整数值val以及指向下一个节点的指针next
*/
typedef struct ListNode ListNode;
struct ListNode {
int val;
struct ListNode *next;
};
/**
* 函数mergeTwoLists接收两个单链表（list1和list2）作为参数，
* 合并这两个已排序的链表，并返回合并后的新链表，新链表中的元素仍按升序排列。
*
* 思路：
* 1. 创建新的链表用于存放合并后的节点，初始化新链表头结点和尾结点。
* 2. 使用while循环比较两个链表当前节点的值，将较小值的节点添加到新链表中。
* 3. 当某个链表遍历完后，将另一个未遍历完链表的剩余部分添加到新链表尾部。
* 4. 最后，释放初始分配给新链表头结点的空间，并返回新链表的第二个节点（实际内容的起始节点）。
*/
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
// 判断输入链表是否为空
if (list1 == NULL) {
return list2;
}
if (list2 == NULL) {
return list1;
}
// 创建临时指针保存原始链表，避免改变它们
ListNode* l1 = list1;
ListNode* l2 = list2;
// 分配内存创建新链表的头结点和尾结点
ListNode *Newhead, *Newtail;
Newhead = Newtail = (ListNode*)malloc(sizeof(ListNode));
// 注意：这里实际上创建了一个空节点作为占位符，其next指针将指向实际的第一个合并节点
// 循环遍历两个链表，将较小值的节点依次添加到新链表中
while (l1 && l2) {
if (l1->val < l2->val) {
Newtail->next = l1;
Newtail = Newtail->next;
l1 = l1->next;
} else {
Newtail->next = l2;
Newtail = Newtail->next;
l2 = l2->next;
}
}
// 将剩余未遍历完的链表连接到新链表尾部
if (l1) {
Newtail->next = l1;
}
if (l2) {
Newtail->next = l2;
}
// 获取新链表的实际头部（即第一个有效节点），释放占位头结点的空间
ListNode* next = Newhead->next;
free(Newhead);
Newhead = NULL; // 可选，置空便于调试或后续操作
// 返回合并后的新链表的实际头部节点
return next;
}
好文阅读
发表评论