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