题目描述
blablabla
样例
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* merge(ListNode* L1, ListNode* L2) {
ListNode* dummy = new ListNode(-1); // 创建一个虚拟的节点,调用构造函数,指向空集
ListNode* tail = dummy; //定义一个节点类型的指针tail,指向dummy
while (L1&&L2)
{
if (L1->val < L2->val) // 如果L1指向的节点的值<L2指向的节点的值,就把L1指向的节点链入新链表,同时L1后移指向下一个节点
{
tail->next = L1; // tail的next指针存放的是新链入的节点的地址
tail = tail->next;// tail指向新链入的节点
L1 = L1->next;
}
else
{
tail->next = L2;
L2 = L2->next;
tail = tail->next;//更新尾节点的地址
}
}
// 至少有一个链表为空
if (L1)
{
tail->next = L1;
tail = tail->next;
}
if (L2)
{
tail->next = L2;
tail = tail->next;
}
return dummy->next; // 返回虚拟头节点的next指针,即返回指向新链表的第一个节点指针,也就是新链表的第一个节点的地址
}
};
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla