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

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 会根据选择的语言给出了一个类的定义或者函数的定义，然后在其中实现  合并两个有序链表 的解题过程。这次我使用 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 节点的指针 移动到下一个元素。

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

代码实现

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;
}

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

提交结果

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

喜欢就点在看哦~