合并两个排序的链表的递归解
本文最后更新于 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:递归,将递归结果赋值到链表未整合部分的末端

思想简述:使用二者初始值最小的链表作为主链表,从末端往前进行整合,将整合好的部分替换掉已经被整合的部分

函数返回:返回初始结点值小的链表,由于没有使用额外辅助空间,故空间复杂度较小

缺点:耗时高

上一篇
下一篇