关于leetcode:每日一练14合并两个排序的链表

title: 每日一练（14）：合并两个排序的链表

categories:[剑指 offer]

tags:[每日一练]

date: 2022/01/27

每日一练（14）：合并两个排序的链表

输出两个递增排序的链表，合并这两个链表并使新链表中的节点依然是递增排序的。

示例 1：

输出：1->2->4, 1->3->4

输入：1->1->2->3->4->4

限度：

0 <= 链表长度 <= 1000

起源：力扣（LeetCode）

链接：https://leetcode-cn.com/probl…

办法一：迭代

咱们的目标是将两个有序链表合并成一个有序链表，因而，咱们的每次操作都是获取 l1 指向的结点和 l2 指向的结点中，值较小的结点。迭代和递归都是如此。

应用迭代的时候

• 为了将第一个结点与其余结点对立解决，个别会定义一个头结点。

应用递归的时候

• 咱们往往能够利用递归函数的返回值，将解决好的链表的第一个结点，作为返回值返回到上一级。
• 上一级函数则间接将失去的返回值，链接在以后结点的 next 即可。

迭代

• 定义头结点
• 若 l1 指向的结点值 < l2 指向的结点值，则将 l1 链接到头结点的 next 地位
• 否则将 l2 链接到头结点的 next 地位
• 循环进行，直至 l1 或 l2 为 NULL
• 最初，将 l1 或 l2 中剩下的局部，链接到头结点前面

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {ListNode *head = new ListNode(0);
    ListNode *ret = head;
    while (l1 != NULL && l2 != NULL) {if (l1->val < l2-> val) {
            head->next = l1;
            l1 = l1->next;
        } else {
            head->next = l2;
            l2 = l2->next;
        }
        head = head->next;
    }
    head->next = l1 == NULL ? l2 : l1;
    return ret->next;
}

办法二：递归

编写递归的第一步，该当是明确以后函数该当实现的性能。

函数性能

• 返回 l1 指向的结点和 l2 指向的结点中，值较小的结点
• 并将从上级函数取得的返回值，链接到以后结点尾部

函数完结条件

• 当 l1 为空，或 l2 为空，函数完结
• 返回 l1 或 l2 中剩下的局部

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {if (!l1 || !l2) {    // 链表判空
        return (!l2 ? l1 : l2);
    }
    if (l1->val < l2->val) {l1->next = mergeTwoLists(l1->next, l2); // 递归
        return l1;
    } else {l2->next = mergeTwoLists(l1, l2->next);    // 递归
        return l2;
    }
}