网站建设推广合同书,网站开发的需求分析书,wordpress cdn加速插件,江西做网站目录
题目
图解
方法一
方法二
代码(解析在注释中)
方法一 编辑方法二 题目
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1#xff1a; 输入#xff1a;l1 [1,2,4], l2 [1,3,4]
输出#xff1a;[1,1…目录
题目
图解
方法一
方法二
代码(解析在注释中)
方法一 编辑方法二 题目
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 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;// 初始化新链表的头结点和尾结点为NULLListNode *Newhead, *Newtail;Newhead Newtail NULL;// 使用while循环遍历两个链表直到其中一个链表遍历完为止while (l1 l2) {// 比较当前节点的值大小将较小值的节点添加到新链表中if (l1-val l2-val) {// 如果新链表还未添加过节点则设置新链表的头结点和尾结点都为l1if (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;
}
