LeetCode (21):合并两个有序链表

栏目: IT技术 · 发布时间: 3年前

1、 LeetCode | 2.两数相加

2、 LeetCode | 206.反转链表

3、 LeetCode | 1.两数之和

4、 LeetCode | 703.数据流中的第K大元素

5、 LeetCode | 232.用栈实现队列

6、 LeetCode | 225.用队列实现栈

7、 LeetCode | 20.有效的括号

8、 LeetCode | 141.环形链表

9、 LeetCode | 24.两两交换链表中的节点

这次来写一下 LeetCode 的第 21 题,合并两个有序链表。

题目描述

题目直接从 LeetCode 上截图过来,题目如下:

LeetCode (21):合并两个有序链表

上面的题就是 合并两个有序链表 题目的截图,同时 LeetCode 会根据选择的语言给出了一个类的定义或者函数的定义,然后在其中实现  合并两个有序链表 的解题过程。这次我使用 C 语言来进行完成。

C 语言给出的函数定义如下:

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* struct ListNode *next;

* };

*/



struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){


}

通过函数定义可以看出,mergeTwoLists 函数的参数是两个单向链表,然后返回值也是一个链表,我们要做的就是把两个有序的链表合并成一个新的有序链表。

问题分析

这个题目中提供的两个链表本身就是有序的链表,只要我们把链表的节点逐个的遍历并比较一遍,就可以合并为另外一个有序的列表。

我们来看一下下面的两幅图,当 链表 l1 节点上的值 链表 l2 节点上的值 进行比较时,只要 l1 节点上的值  小于等于  链表 l2 节点上的值 ,那么我们就取 链表 l1 节点上的值  放入 新的链表节点 上,并将指向 链表 l1 节点的指针  移动到下一个元素 反之,则将 链表 l2 节点上的值 放入 新的链表节点 上,并将指向 链表 l2 节点的指针 移动到下一个元素。

LeetCode (21):合并两个有序链表

LeetCode (21):合并两个有序链表

在两个有序链表节点个数相同的时候,这样做是没有问题的,如果两个有序链表节点个数不相同的话,那么当一个链表的所有节点已经遍历完,那么就去遍历剩下的一条链表即可。如下图。

LeetCode (21):合并两个有序链表

代码实现

C 语言的代码如下:

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* struct ListNode *next;

* };

*/

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){

struct ListNode* ll1 = l1;

struct ListNode* ll2 = l2;


struct ListNode* ll = NULL;

struct ListNode* cur = NULL;


while (ll1 != NULL || ll2 != NULL) {

struct ListNode* tmp = (struct ListNode*)malloc(sizeof(struct ListNode));

tmp->next = NULL;


// 初始化新节点的指针

if (cur == NULL) {

cur = tmp;

ll = tmp;

} else { // 当前节点指针的下一个节点

cur->next = tmp;

cur = tmp;

}

// ll1为NULL后,遍历链表ll2

if (ll1 == NULL) {

tmp->val = ll2->val;

ll2 = ll2->next;

continue;

}

// ll2为NULL后,遍历链表ll1

if (ll2 == NULL) {

tmp->val = ll1->val;

ll1 = ll1->next;

continue;

}

// ll1节点的当前值小于等于ll2节点的当前值

// 则把ll1节点的当前值放入tmp节点中

if (ll1->val <= ll2->val) {

tmp->val = ll1->val;

ll1 = ll1->next;

} else {

tmp->val = ll2->val;

ll2 = ll2->next;

}

}


return ll;

}

代码中有了详细的注释,就不对代码做过多的解释了。

提交结果

在写完代码后,点击右下角的 “ 执行代码 ”,然后观察  “输出” 和 “预期结果”  是否一致,一致的话就点击 “ 提交 ” 按钮。点击 “提交” 按钮后,系统会使用更多的测试用例来测试我们写的函数体, 如果所有的测试用例都通过了,那么就会给出 “通过” 的字样, 如果没有通过,会给出失败的那一组测试用例,我们可以根据给出的测试用例来继续修改代码 。我们的代码提交后的截图如下:

LeetCode (21):合并两个有序链表

LeetCode (21):合并两个有序链表

喜欢就点在看哦~


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

咨询的奥秘

咨询的奥秘

[美] 杰拉尔德·温伯格(Gerald M.Weinberg) / 李彤、关山松 / 清华大学出版社 / 2004 / 29.00元

一起来看看 《咨询的奥秘》 这本书的介绍吧!

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

HTML 编码/解码
HTML 编码/解码

HTML 编码/解码

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器