题目描述

合并两个链表

样例

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) {}
 * };
 */
//链表通常只能表示当前的结点 下文中的l1就是一个链表 l1->val表示只能当前的链表的第一个值
//l1->next 表示下一个结点 l1->next->next表示下下个结点 
class Solution {
public:
    ListNode* merge(ListNode* l1, ListNode* l2) {

            auto dumy = new  ListNode(-1);//创建一个新的链表 定义一个头节点
            auto cur = dumy;//定义一个结点指针指向头节点
            while(l1&&l2)//当遍历到哪个链表最后一个结点时就会跳出循环
            //因为在下面的循环中 l1和l2链表的长度会发生改变 
            {
                if(l1->val<l2->val)//判断当前的值哪个大
                {
                    cur->next = l1;//将当前数据小的链表插入到新链表中
                    l1 = l1->next;//将l1链表后面的数据覆盖前面的数据  当指到了最后一个结点时它会指向空！！！
                    //成了一个减了一个结点的链表
                }
                else
                {
                    cur->next = l2;
                    l2 = l2->next;//同上
                }
                cur = cur->next;// 因为新链表已经插入了一个元素 所以我们要指向下一个位置等待元素的插入
            }
            if(l1) cur->next = l1;//如果l1没到最后一个结点 在cur的下个结点就是指向（经历了缩减一些结点后的）l1的链表
            if(l2) cur->next = l2;//同上
             return dumy->next;//返回头节点指向的下一个结点 及是新链表
    }
};

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla