企业官网建设流程全解析

题目描述

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

解题思路

1. 递归终止条件：如果其中一条链表为空，直接返回另一条链表

2. 比较两个链表当前头节点的值，选取更小的节点作为当前节点

3. 把选中节点的 next 指向剩下链表合并后的结果

4. 返回当前节点，完成拼接

复杂度分析

时间复杂度：O(n+m)，n、m为两条链表节点总数，每个节点访问一次

空间复杂度：O(n+m)，递归调用栈占用空间

踩坑总结

1. 注意判断链表为空 NULL ，不判断会空指针报错

2. 递归是从上往下拼接，不要搞反节点指向

3. 递归写法适合理解链表，大数据量担心栈溢出可以改用迭代写法

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { if(list1 == NULL) return list2; if(list2 == NULL) return list1; if(list1->val < list2->val){ list1->next = mergeTwoLists(list1->next, list2); return list1; }else{ list2->next = mergeTwoLists(list1, list2->next); return list2; } }