合并k个已排序的链表

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

这个代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    
    ListNode* mergetK(ListNode *A,ListNode *B)
    {
        ListNode *C = nullptr;
        ListNode *ans = nullptr;
        while(A != nullptr && B != nullptr)
        {
            ListNode *s = new ListNode(0);
            if(A->val > B->val)
            {
                s->val = B->val;
                s->next = nullptr;
                B = B->next;
            }
            else
            {
                s->val = A->val;
                s->next = nullptr;
                A = A->next;
            }
            
            if(C == nullptr)
            {
                C = s;
                ans = C;
            }
            else
            {
                C->next = s;
                C = C->next;
            }
        }
        
        while(A != nullptr)
        {
            ListNode *s = new ListNode(0);
            s->val = A->val;
            s->next = nullptr;
            if(C == nullptr)
            {
                C = s;
                ans = C;
            }
            else
            {
                C->next = s;
                C = C->next;
            }
            A = A->next;
            
        }
        
        
        while(B != nullptr)
        {
            ListNode *s = new ListNode(0);
            s->val = B->val;
            s->next = nullptr;
            if(C == nullptr)
            {
                C = s;
                ans = C;
            }
            else
            {
                C->next = s;
                C = C->next;
            }
            B = B->next;
            
        }
        
        return ans;
    }
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        if(lists.empty())
        {
            return nullptr;
        }
        
        ListNode *ans;
        ans = lists[0];
        for(int i=1;i<lists.size();i++)
        {
           ans = mergetK(ans,lists[i]);
        }
        return ans;
    }
};

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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    
    ListNode* mergetK(ListNode *A,ListNode *B)
    {
        ListNode *pA = A;
        ListNode *pB = B;
        ListNode *ans = nullptr;
        ListNode *head = nullptr;
        while(A != nullptr && B != nullptr)
        {
           if(A->val <= B->val)
           {
               if(ans == nullptr)
               {
                   ans = A;
                   head = A;
               }
               else
               {
                   head->next = A;
                   head = head->next;
               }
               
               //pA = A;
               A = A->next; 
           }
           else
           {
               if(ans == nullptr)
               {
                   ans = B;
                   head = B;
               }
                else
               {
                   head->next = B;
                   head = head->next;
               }
               //pB = B;
               B = B->next;
           }
        }
        
        if(A != nullptr)
        {
           
            head->next = A;
        }
        
        
        if(B != nullptr)
        {
            head->next = B;
        }
        
        return ans;
    }
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        if(lists.empty())
        {
            return nullptr;
        }
        
        ListNode *ans;
        ans = lists[0];
        for(int i=1;i<lists.size();i++)
        {
           if(lists[i] == nullptr)
           {
               continue;
           }
           ans = mergetK(ans,lists[i]);
        }
        return ans;
    }
};

我去，超时.....

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

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

遍历 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}]

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

合并两个有序链表代码:

struct ListNode 
{
     int val;
     ListNode *next;
     ListNode(int x) : val(x), next(NULL) {}
};

ListNode* merge(ListNode *A,ListNode *B)
{
    //特判 (A=nullptr && B=nullptr) 或者
    // (A=nullptr && B!=nullptr) 或者 (A!=nullptr && B=nullptr)
    if(A == nullptr || B == nullptr)
    {
        return A==nullptr ? B:A;
    }
    
    ListNode *head = nullptr;
    ListNode *ans  = nullptr;
    

    while(A != nullptr && B != nullptr)
    {
        if(A->val <= B->val)
        {
            if(ans == nullptr)
            {
                ans = A;
                head = A;
            }
            else
            {
                head->next = A;
                head = head->next;
            }
            A = A->next;
        }
        else
        {
            if(ans == nullptr)
            {
                ans = B;
                head = B;
            }
            else
            {
                head->next = B;
                head = head->next;
            }
            B = B->next;
        }
    }

    if(A != nullptr)
    {
        head->next = A;
    }

    if(B != nullptr)
    {
        head->next = B;
    }
    

    retrun ans;
}

二分的思路及代码：

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

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

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

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

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

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

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

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

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

        我们继续划分

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

//返回值看我上面画的图
ListNode* binary_lists(vector<ListNode *> &lists,int l,int r)
{
    
    //先写边界条件(出口)
    if(l == r)
    {
        return lists[l];
    }
    if(l > r)
    {
        return nullptr;
    }   

    int mid = (l+r)/2;
    
    //合并 A和B    因为回溯到这个点的时候需要合并A和B
    return merge(binary_lists(lists,l,mid),binary_lists(lists,mid+1,r));
    
}

 okk...

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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *ans1;
    ListNode* merget(ListNode *A,ListNode *B)
    {
        if(A == nullptr || B == nullptr)
        {
            return A == nullptr ? B:A;
        }
        ListNode *pA = A;
        ListNode *pB = B;
        ListNode *ans = nullptr;
        ListNode *head = nullptr;
        while(A != nullptr && B != nullptr)
        {
           if(A->val <= B->val)
           {
               if(ans == nullptr)
               {
                   ans = A;
                   head = A;
               }
               else
               {
                   head->next = A;
                   head = head->next;
               }
               
               //pA = A;
               A = A->next; 
           }
           else
           {
               if(ans == nullptr)
               {
                   ans = B;
                   head = B;
               }
                else
               {
                   head->next = B;
                   head = head->next;
               }
               //pB = B;
               B = B->next;
           }
        }
        
        if(A != nullptr)
        {
           
            head->next = A;
        }
        
        
        if(B != nullptr)
        {
            head->next = B;
        }
        
        return ans;
    }
    
    ListNode* merList(vector<ListNode *> &lists,int l,int r)
    {
        if(l == r)    //只有一条
        {
            return lists[l];
        }
        if( l > r)
        {
            return nullptr;
        }
        int mid = (l + r)/2;
        
        return merget(merList(lists,l,mid),merList(lists,mid+1,r));
    }
   
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        if(lists.empty())
        {
            return nullptr;
        }
        
       
//       ans = lists[0];
//         for(int i=1;i<lists.size();i++)
//         {
//            if(lists[i] == nullptr)
//            {
//                continue;
//            }
//            ans = mergetK(ans,lists[i]);
//         }        
        
        return merList(lists,0,lists.size()-1);
    }
};

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

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