网站开发选题背景,中资建筑信息平台,省企联网站建设要求,国产crm目录
描述
题目分析 描述 输入两个递增的链表#xff0c;单个链表的长度为n#xff0c;合并这两个链表并使新链表中的节点仍然是递增排序的。 数据范围#xff1a;0≤n≤1000#xff0c;1000≤节点值≤1000 要求#xff1a;空间复杂度 O(1)#xff0c;时间复杂…目录
描述
题目分析 描述 输入两个递增的链表单个链表的长度为n合并这两个链表并使新链表中的节点仍然是递增排序的。 数据范围0≤n≤10001000≤节点值≤1000 要求空间复杂度 O(1)时间复杂度 O(n)
如输入{1,3,5},{2,4,6}时合并后的链表为{1,2,3,4,5,6}所以对应的输出为{1,2,3,4,5,6}转换过程如下图所示 或输入{-1,2,4},{1,3,4}时合并后的链表为{-1,1,2,3,4,4}所以对应的输出为{-1,1,2,3,4,4}转换过程如下图所示 示例1
输入{1,3,5},{2,4,6}返回值{1,2,3,4,5,6}
示例2
输入{},{}返回值{}
示例3
输入{-1,2,4},{1,3,4}返回值{-1,1,2,3,4,4}
题目分析
方法一迭代版本求解
初始化定义cur指向新链表的头结点 操作
如果l1指向的结点值小于等于l2指向的结点值则将l1指向的结点值链接到cur的next指针然后l1指向下一个结点值否则让l2指向下一个结点值循环步骤1,2直到l1或者l2为nullptr将l1或者l2剩下的部分链接到cur的后面
技巧 一般创建单链表都会设一个虚拟头结点也叫哨兵因为这样每一个结点都有一个前驱结点。
代码
class Solution {
public:ListNode* Merge(ListNode* pHead1, ListNode* pHead2){ListNode *vhead new ListNode(-1);ListNode *cur vhead;while (pHead1 pHead2) {if (pHead1-val pHead2-val) {cur-next pHead1;pHead1 pHead1-next;}else {cur-next pHead2;pHead2 pHead2-next;}cur cur-next;}cur-next pHead1 ? pHead1 : pHead2;return vhead-next;}
};
时间复杂度O(mn),mn分别为两个单链表的长度 空间复杂度O(1)
方法二递归版本 方法一的迭代版本很好理解代码也好写。但是有必要介绍一下递归版本可以练习递归代码。 写递归代码最重要的要明白递归函数的功能。可以不必关心递归函数的具体实现。 比如这个ListNode* Merge(ListNode* pHead1, ListNode* pHead2) 函数功能合并两个单链表返回两个单链表头结点值小的那个节点。
如果知道了这个函数功能那么接下来需要考虑2个问题 递归函数结束的条件是什么 递归函数一定是缩小递归区间的那么下一步的递归区间是什么 对于问题1.对于链表就是如果为空返回什么 对于问题2跟迭代方法中的一样如果PHead1的所指节点值小于等于pHead2所指的结点值那么phead1后续节点和pHead节点继续递归
代码
class Solution {
public:ListNode* Merge(ListNode* pHead1, ListNode* pHead2){if (!pHead1) return pHead2;if (!pHead2) return pHead1;if (pHead1-val pHead2-val) {pHead1-next Merge(pHead1-next, pHead2);return pHead1;}else {pHead2-next Merge(pHead1, pHead2-next);return pHead2;}}
};
时间复杂度O(mn) 空间复杂度O(mn),每一次递归递归栈都会保存一个变量最差情况会保存(mn)个变量
