本文最后更新于 1394 天前,其中的信息可能已经有所发展或是发生改变。
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (!l1 || !l2) return !l1 ? l2 : l1;
if (l1->val < l2->val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
} else {
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
代码来源:https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/
Line2:判空,递归终点,返回 l1 和 l2 中的非空结点,若都为空结点则返回 l2
Line3-9:递归,将递归结果赋值到链表未整合部分的末端
思想简述:使用二者初始值最小的链表作为主链表,从末端往前进行整合,将整合好的部分替换掉已经被整合的部分
函数返回:返回初始结点值小的链表,由于没有使用额外辅助空间,故空间复杂度较小
缺点:耗时高