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