描述
输入两个递增的链表,单个链表的长度为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}
题解
- 1. 确定头节点,确保left->val <= right->val
- 2. 使用指针head指向left,让left = left->next,并记录tail节点作为新节点的末尾节点
- 3. 循环比较left->val和right->val,直到left和right都为空
- 如果left或者right为空,则直接取left或者right的下一个节点作为tail->next节点
- 如果left和right都不会空,则让tail->next指向值较小的一个节点,并更新left或者right节点为其next
struct ListNode
{
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(nullptr)
{
}
};
class Solution
{
public:
ListNode *Merge(ListNode *left, ListNode *right)
{
if (left == nullptr)
{
return right;
}
if (right == nullptr)
{
return left;
}
if (left->val > right->val)
{
return Merge(right, left);
}
ListNode *head = left;
ListNode *tail_node = left;
left = left->next;
while (left != nullptr || right != nullptr)
{
if (left == nullptr)
{
tail_node->next = right;
right = right->next;
tail_node = tail_node->next;
}
else if (right == nullptr)
{
tail_node->next = left;
left = left->next;
tail_node = tail_node->next;
}
else
{
if (left->val < right->val)
{
auto next = left->next;
tail_node->next = left;
left = next;
tail_node = tail_node->next;
}
else
{
auto next = right->next;
tail_node->next = right;
right = next;
tail_node = tail_node->next;
}
}
}
return head;
}
};