文章目录
- 前言
- 题目
- 1. 解决方案一
- 1.1 思路概述
- 1.2 源码
- 2. 解决方案二
- 2.1 思路阐述
- 2.2 源码
- 总结
前言
这道题采用两种方式，一种是直接插入法，还有一种就是递归调用。
题目
输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。
数据范围： 0≤n≤1000，−1000≤节点值≤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.1 思路概述
合并链表的过程就是插入节点的过程，不过是双链表遍历。
首先判断两个链表的最小节点谁的最小，那么链表首节点小的作为基链表，另一个链表进行比较与插入。
一般链表题都要添加一个头结点，作为哨兵节点，这样的好处是确保每一个节点都有一个前置节点。
对于题目中的特殊情况，空链表这种，我们得单独拎出来判断。如果一个链表是空链表，则直接返回另一个非空链表；如果两个链表都为空，则直接返回空链表。
正常判断的情况，这里以pHead1为基链表的情况（也就是pHead1的第一个节点小于pHead2的第一个节点）为例。
我们通过一个bool类型变量来确定基链表判断逻辑。
如果pHead2链表的值小于pHead1指向的节点的下一个值，就进行插入。比如，1,3,5的基链表，2,4,6链表往里面插入，因为我们已经通过首节点判断出pHead2的首节点肯定比pHead1的节点大，我们只需要找到pHead1中第一个比pHead2中要插入到pHead1的节点大的节点即可。所以这里用到了pHead->next->val。
后面就是断链和插入的操作，再接着就是双链表遍历，即调整双链表中指针的位置。
如果pHead1>pHead2的情况，那么逻辑是基本一致的，这里就不在赘述。
1.2 源码
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param pHead1 ListNode类
* @param pHead2 ListNode类
* @return ListNode类
*/
ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
ListNode* rec = new ListNode(-1);
if (!pHead1 && !pHead2) {
return nullptr;
}
if (!pHead1 && pHead2) {
return pHead2;
}
if (pHead1 && !pHead2) {
return pHead1;
}
//比较链表大小
bool firstListBig = true;
if (pHead1->val > pHead2->val) {
firstListBig = true;
rec->next = pHead2;
} else {
firstListBig = false;
rec->next = pHead1;
}
//第二个链表大的情况
if (!firstListBig) {
while (pHead2 && pHead1) {
//如果小链表后面没有节点了，则大链表直接加到小链表后
if (!pHead1->next) {
pHead1->next = pHead2;
break;
}
ListNode* tempNode = pHead2->next;
if (pHead2->val <= pHead1->next->val) {
pHead2->next = pHead1->next;
pHead1->next = pHead2;
pHead2 = tempNode;
pHead1 = pHead1->next;
} else {
pHead1 = pHead1->next;
if (!pHead1->next) {
pHead1->next = pHead2;
break;
}
}
}
}
else //第二个链表小的情况
{
while (pHead2 && pHead1) {
if (!pHead2->next) {
pHead2->next = pHead1;
break;
}
ListNode* tempNode = pHead1->next;
if (pHead1->val <= pHead2->next->val) {
pHead1->next = pHead2->next;
pHead2->next = pHead1;
pHead1 = tempNode;
pHead2 = pHead2->next;
} else {
pHead2 = pHead2->next;
if (!pHead2->next) {
pHead2->next = pHead1;
break;
}
}
}
}
return rec->next;
}
};
2. 解决方案二
2.1 思路阐述
使用递归的方式进行处理。
写递归代码，最重要的要明白递归函数的功能。可以不必关心递归函数的具体实现。
比如这个ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
函数功能：合并两个单链表，返回两个单链表头结点值小的那个节点。
如果知道了这个函数功能，那么接下来需要考虑2个问题：
递归函数结束的条件是什么？（这个非常重要，一般第一个就要写它）
递归函数一定是缩小递归区间的，那么下一步的递归区间是什么？
对于问题1.对于链表就是，如果为空，返回什么
对于问题2，跟迭代方法中的一样，如果PHead1的所指节点值小于等于pHead2所指的结点值，那么phead1后续节点和pHead节点继续递归。这个就类似于去找到一个pHead1中所指节点第一个比pHead2所指节点大的节点。
时间复杂度：O(m+n)
空间复杂度：O(m+n),每一次递归，递归栈都会保存一个变量，最差情况会保存(m+n)个变量
递归的一个大致流程，我画了一下，其实大家可以自己debug一下就知道了
2.2 源码
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;
}
}
};
总结
这道题的第一个迭代方法是我最先想到的，代码也比较好写。第二个方法是看题解，这里整合下来作为参考。
