LeetCode | 21.合并两个有序链表

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

题目描述

题目直接从 LeetCode 上截图过来，题目如下：

image

上面的题就是 合并两个有序链表 题目的截图，同时 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 节点的指针 移动到下一个元素。

image image

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

image.gif

代码实现

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

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

提交结果

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

image

---

微信中搜索 “码农UP2U” 关注我的公众号吧！！！