• 合并k个已排序的链表

     ojbk...开始以为这题没有内存要求,所以就用来一个很简单的方法合并。创建第三条链表，结果部分案例过不去。

    这个代码：

    1. /**
    2.  * Definition for singly-linked list.
    3.  * struct ListNode {
    4.  *     int val;
    5.  *     ListNode *next;
    6.  *     ListNode(int x) : val(x), next(NULL) {}
    7.  * };
    8.  */
    9. class Solution {
    10. public:
    11.     
    12.     ListNode* mergetK(ListNode *A,ListNode *B)
    13.     {
    14.         ListNode *C = nullptr;
    15.         ListNode *ans = nullptr;
    16.         while(A != nullptr && B != nullptr)
    17.         {
    18.             ListNode *s = new ListNode(0);
    19.             if(A->val > B->val)
    20.             {
    21.                 s->val = B->val;
    22.                 s->next = nullptr;
    23.                 B = B->next;
    24.             }
    25.             else
    26.             {
    27.                 s->val = A->val;
    28.                 s->next = nullptr;
    29.                 A = A->next;
    30.             }
    31.             
    32.             if(C == nullptr)
    33.             {
    34.                 C = s;
    35.                 ans = C;
    36.             }
    37.             else
    38.             {
    39.                 C->next = s;
    40.                 C = C->next;
    41.             }
    42.         }
    43.         
    44.         while(A != nullptr)
    45.         {
    46.             ListNode *s = new ListNode(0);
    47.             s->val = A->val;
    48.             s->next = nullptr;
    49.             if(C == nullptr)
    50.             {
    51.                 C = s;
    52.                 ans = C;
    53.             }
    54.             else
    55.             {
    56.                 C->next = s;
    57.                 C = C->next;
    58.             }
    59.             A = A->next;
    60.             
    61.         }
    62.         
    63.         
    64.         while(B != nullptr)
    65.         {
    66.             ListNode *s = new ListNode(0);
    67.             s->val = B->val;
    68.             s->next = nullptr;
    69.             if(C == nullptr)
    70.             {
    71.                 C = s;
    72.                 ans = C;
    73.             }
    74.             else
    75.             {
    76.                 C->next = s;
    77.                 C = C->next;
    78.             }
    79.             B = B->next;
    80.             
    81.         }
    82.         
    83.         return ans;
    84.     }
    85.     ListNode *mergeKLists(vector &lists) {
    86.         if(lists.empty())
    87.         {
    88.             return nullptr;
    89.         }
    90.         
    91.         ListNode *ans;
    92.         ans = lists[0];
    93.         for(int i=1;isize();i++)
    94.         {
    95.            ans = mergetK(ans,lists[i]);
    96.         }
    97.         return ans;
    98.     }
    99. };

     好吧，看来不能创建新的节点，只能用辅助指针了。。。。。(这题就是合并两个有序链表，水题)

    1. /**
    2.  * Definition for singly-linked list.
    3.  * struct ListNode {
    4.  *     int val;
    5.  *     ListNode *next;
    6.  *     ListNode(int x) : val(x), next(NULL) {}
    7.  * };
    8.  */
    9. class Solution {
    10. public:
    11.     
    12.     ListNode* mergetK(ListNode *A,ListNode *B)
    13.     {
    14.         ListNode *pA = A;
    15.         ListNode *pB = B;
    16.         ListNode *ans = nullptr;
    17.         ListNode *head = nullptr;
    18.         while(A != nullptr && B != nullptr)
    19.         {
    20.            if(A->val <= B->val)
    21.            {
    22.                if(ans == nullptr)
    23.                {
    24.                    ans = A;
    25.                    head = A;
    26.                }
    27.                else
    28.                {
    29.                    head->next = A;
    30.                    head = head->next;
    31.                }
    32.                
    33.                //pA = A;
    34.                A = A->next; 
    35.            }
    36.            else
    37.            {
    38.                if(ans == nullptr)
    39.                {
    40.                    ans = B;
    41.                    head = B;
    42.                }
    43.                 else
    44.                {
    45.                    head->next = B;
    46.                    head = head->next;
    47.                }
    48.                //pB = B;
    49.                B = B->next;
    50.            }
    51.         }
    52.         
    53.         if(A != nullptr)
    54.         {
    55.            
    56.             head->next = A;
    57.         }
    58.         
    59.         
    60.         if(B != nullptr)
    61.         {
    62.             head->next = B;
    63.         }
    64.         
    65.         return ans;
    66.     }
    67.     ListNode *mergeKLists(vector &lists) {
    68.         if(lists.empty())
    69.         {
    70.             return nullptr;
    71.         }
    72.         
    73.         ListNode *ans;
    74.         ans = lists[0];
    75.         for(int i=1;isize();i++)
    76.         {
    77.            if(lists[i] == nullptr)
    78.            {
    79.                continue;
    80.            }
    81.            ans = mergetK(ans,lists[i]);
    82.         }
    83.         return ans;
    84.     }
    85. };

    我去，超时.....

    看来这题没有想的那么简单呀....

    分析下代码的时间复杂度，，，，

    遍历 litsts  O(n)

    内部:等于遍历了一遍 链表  O(n+m)

    这么算:O(n^2) 

    看题目要求的是时间复杂度   O(nlogk)

    k是链表的个数：说明只能从 遍历 litsts开🔪了。。。。

    根据经验，合并两个有序链表时间复杂度最优 O(n+m) 再一次说明  只能从 遍历 litsts优化了

    等等，logK对数时间，第一反应应该是二分吧。我去，说不定可以解决

    二分的前提：保证有序，nice，题目的条件刚好是有序的(因为数组下标是递增的呀)

    优化后：

    我操，终于过了。。。。。感动，落泪。一个小时呜呜....

    两个链表的合并:（前面的代码有点小bug,有一种情况需要特殊处理）

    当一个链表尾空时:(此时应该不需要合并)

    [{-9},{},{-10,-8,-2,-1,2},{-10,-9,-7,-6,-5,-2,-2,1,4},{-7,-7,-1,0,4},{},{-4,0},{-9,-6,-5,-5,-2,2,3,3}]

    更改:做个特判，两个有序链表的合并就不说了，只要你认真一点就一定能写出来。

    合并两个有序链表代码:

    1. struct ListNode 
    2. {
    3.      int val;
    4.      ListNode *next;
    5.      ListNode(int x) : val(x), next(NULL) {}
    6. };
    7.  
    8. ListNode* merge(ListNode *A,ListNode *B)
    9. {
    10.     //特判 (A=nullptr && B=nullptr) 或者
    11.     // (A=nullptr && B!=nullptr) 或者 (A!=nullptr && B=nullptr)
    12.     if(A == nullptr || B == nullptr)
    13.     {
    14.         return A==nullptr ? B:A;
    15.     }
    16.     
    17.     ListNode *head = nullptr;
    18.     ListNode *ans  = nullptr;
    19.     
    20.  
    21.     while(A != nullptr && B != nullptr)
    22.     {
    23.         if(A->val <= B->val)
    24.         {
    25.             if(ans == nullptr)
    26.             {
    27.                 ans = A;
    28.                 head = A;
    29.             }
    30.             else
    31.             {
    32.                 head->next = A;
    33.                 head = head->next;
    34.             }
    35.             A = A->next;
    36.         }
    37.         else
    38.         {
    39.             if(ans == nullptr)
    40.             {
    41.                 ans = B;
    42.                 head = B;
    43.             }
    44.             else
    45.             {
    46.                 head->next = B;
    47.                 head = head->next;
    48.             }
    49.             B = B->next;
    50.         }
    51.     }
    52.  
    53.     if(A != nullptr)
    54.     {
    55.         head->next = A;
    56.     }
    57.  
    58.     if(B != nullptr)
    59.     {
    60.         head->next = B;
    61.     }
    62.     
    63.  
    64.     retrun ans;
    65. }

    二分的思路及代码：

    对于二分有两种方法:递归(推荐使用)   非递归

    通常我们使用递归就行，好分析，好写代码

    我们先看一个例子来分析:

            先分成两半: A和B的处理过程一定要是一样的(或者说将一个整体划分为两个与这个整体相同的子问题)

            假设将A和B成最小的子问题了，此时我们应该干嘛？？？？

            当然是进行链表合并咯。。。。

            好的我们来合并吧，又看，A和B还没划分到最小呀。(递归是一个自顶向下的过程)

            为什么我这里说要把A和B看作最小的子问题呢？？这个是作者对递归的特别理解吧，如果画出解空间，递归是不是需要回溯，当我们回溯到这一层的时候是不是需要合并 A和B.

            ok....为了方便理解我们不妨就把每次状态都当作最小问题，对于最小问题的求解什么样的，我们就怎么处理就行了，而且本来就数划分为与子问题一样的问题吗，只是规模遍历而已。

            我们继续划分

            

     

       我们写代码吧(二分代码)

    1. //返回值看我上面画的图
    2. ListNode* binary_lists(vector &lists,int l,int r)
    3. {
    4.     
    5.     //先写边界条件(出口)
    6.     if(l == r)
    7.     {
    8.         return lists[l];
    9.     }
    10.     if(l > r)
    11.     {
    12.         return nullptr;
    13.     }   
    14.  
    15.     int mid = (l+r)/2;
    16.     
    17.     //合并 A和B    因为回溯到这个点的时候需要合并A和B
    18.     return merge(binary_lists(lists,l,mid),binary_lists(lists,mid+1,r));
    19.     
    20. }

     okk...

    我们把所有的代码合在一起吧

    1. /**
    2.  * Definition for singly-linked list.
    3.  * struct ListNode {
    4.  *     int val;
    5.  *     ListNode *next;
    6.  *     ListNode(int x) : val(x), next(NULL) {}
    7.  * };
    8.  */
    9. class Solution {
    10. public:
    11.     ListNode *ans1;
    12.     ListNode* merget(ListNode *A,ListNode *B)
    13.     {
    14.         if(A == nullptr || B == nullptr)
    15.         {
    16.             return A == nullptr ? B:A;
    17.         }
    18.         ListNode *pA = A;
    19.         ListNode *pB = B;
    20.         ListNode *ans = nullptr;
    21.         ListNode *head = nullptr;
    22.         while(A != nullptr && B != nullptr)
    23.         {
    24.            if(A->val <= B->val)
    25.            {
    26.                if(ans == nullptr)
    27.                {
    28.                    ans = A;
    29.                    head = A;
    30.                }
    31.                else
    32.                {
    33.                    head->next = A;
    34.                    head = head->next;
    35.                }
    36.                
    37.                //pA = A;
    38.                A = A->next; 
    39.            }
    40.            else
    41.            {
    42.                if(ans == nullptr)
    43.                {
    44.                    ans = B;
    45.                    head = B;
    46.                }
    47.                 else
    48.                {
    49.                    head->next = B;
    50.                    head = head->next;
    51.                }
    52.                //pB = B;
    53.                B = B->next;
    54.            }
    55.         }
    56.         
    57.         if(A != nullptr)
    58.         {
    59.            
    60.             head->next = A;
    61.         }
    62.         
    63.         
    64.         if(B != nullptr)
    65.         {
    66.             head->next = B;
    67.         }
    68.         
    69.         return ans;
    70.     }
    71.     
    72.     ListNode* merList(vector &lists,int l,int r)
    73.     {
    74.         if(l == r)    //只有一条
    75.         {
    76.             return lists[l];
    77.         }
    78.         if( l > r)
    79.         {
    80.             return nullptr;
    81.         }
    82.         int mid = (l + r)/2;
    83.         
    84.         return merget(merList(lists,l,mid),merList(lists,mid+1,r));
    85.     }
    86.    
    87.     ListNode *mergeKLists(vector &lists) {
    88.         if(lists.empty())
    89.         {
    90.             return nullptr;
    91.         }
    92.         
    93.        
    94. //       ans = lists[0];
    95. //         for(int i=1;i
    96. //         {
    97. //            if(lists[i] == nullptr)
    98. //            {
    99. //                continue;
    100. //            }
    101. //            ans = mergetK(ans,lists[i]);
    102. //         }        
    103.         
    104.         return merList(lists,0,lists.size()-1);
    105.     }
    106. };

      

       小结:创作不易，点个关注支持一下吧

       如果有喜欢C++的同学可以观看作者的其他专栏，全套C++都在更新(从C++基础到Linux系  统编程、网络编程 数据编程等等... 并且有一个完整C++项目)

  • 相关阅读:
    【leetcode】三维形体投影面积 c++
    OSError: [Errno 22] Invalid argument: ‘D:\test\x07‘
    C# 读写文件从用户态切到内核态，到底是个什么流程？
    SkyLight 添加LightingChannelMask功能
    elmentui 查看大图组件 点击图片关闭弹窗方法
    用 Kafka + DolphinDB 实时计算 K 线
    NumPy 数组创建方法与索引访问详解
    MySQL索引详解
    [Power Query] 数据类型转换
    系统集成测试（SIT）/系统测试（ST）/用户验收测试（UAT）
  • 原文地址：https://blog.csdn.net/weixin_46120107/article/details/126203583