首页 > 试题广场 >

合并k个已排序的链表

[编程题]合并k个已排序的链表
  • 热度指数：179593 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。

数据范围：节点总数 ，每个节点的val满足
要求：时间复杂度
示例1

输入

[{1,2,3},{4,5,6,7}]

输出

{1,2,3,4,5,6,7}
示例2

输入

[{1,2},{1,4,5},{6}]

输出

{1,1,2,4,5,6}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息
算法知识视频讲解
添加回答
C
加我告诉你蟹黄包秘方头像 加我告诉你蟹黄包秘方
//思路：传入的链表依次合并
struct ListNode* mergeKLists(struct ListNode** lists, int listsLen )
{
    if (lists == NULL)
    {
        return NULL;
    }
    if (listsLen == 0 || listsLen == 1)
    {
        return *lists;
    }

    struct ListNode a = { 0 };
    struct ListNode* t = &a;
    a.next = *lists;

    for (int i = 1; i < listsLen; i++)
    {
        *lists = a.next;
        t = &a;

        while (*lists != NULL && (*(lists + i)) != NULL)
        {
            if ((*lists)->val < (*(lists + i))->val)
            {
                t->next = *lists;
                *lists = (*lists)->next;
            }
            else
            {
                t->next = *(lists + i);
                *(lists + i) = (*(lists + i))->next;
            }

            t = t->next;
        }

        t->next = ((*lists) ? (*lists) : (*(lists + i)));
    }

    return a.next;
}
编辑于 2024-04-19 15:42:46 回复(0)
C
牛客35907575号头像 牛客35907575号
struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) {
    // write code here
    struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
   struct ListNode* tail;
   tail = head;
   int arr[2001] = { 0 };
   for(int i =0;i<listsLen;i++)
   {
   struct ListNode* tmplists = *(lists+i);
    while(tmplists)
    {
       arr[tmplists->val + 1000]++;
       tmplists = tmplists->next;
   }
   }
   for (int i = 0; i < 2001; i++)
   {
       if (arr[i] == 0)
           continue;
       else
           while (arr[i] != 0)
           {
               struct ListNode* tmp = (struct ListNode*)malloc(sizeof(struct ListNode));
               tmp->val = i - 1000;
               tail->next = tmp;
               tmp->next = NULL;
               tail = tail->next;
               arr[i]--;
           }
   }
   return head->next;
}
为什么这里会有问题，下面调试显示的head->next好像没有问题
编辑于 2024-04-15 21:34:04 回复(0)
C
南宫梦凝头像 南宫梦凝 
/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param lists ListNode类一维数组
 * @param listsLen int lists数组长度
 * @return ListNode类
 */
int lenth(struct ListNode* p1, struct ListNode* p2){
    int len = 0;
    while(p1 != NULL){
        len++;
        p1 = p1->next;
    }
    while(p2 != NULL){
        len++;
        p2 = p2->next;
    }
    return len;
}
void mergeSort(struct ListNode* p1, struct ListNode* p2, int len){
    int* B = (int*)malloc(sizeof(int)*len), k = 0;
    struct ListNode* p3, *p4;
    p3 = p1;
    p4 = p2;
    while(p3 != NULL && p4 != NULL){
        if(p3->val <= p4->val){
            B[k++] = p3->val;
            p3 = p3->next;
        }else{
            B[k++] = p4->val;
            p4 = p4->next;
        }
    }
    while(p3 != NULL){
        B[k++] = p3->val;
        p3 = p3->next;
    }
    while(p4 != NULL){
        B[k++] = p4->val;
        p4 = p4->next;
    }
    p3 = p1;
    while(p3->next != NULL){
        p3 = p3->next;
    }
    p3->next = p2;
    for(p3 = p1,k =0;k < len;k++){
        p3->val = B[k];
        p3 = p3->next;
    }
    free(B);
} 
struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) {
    // write code here
    struct ListNode* p1 = NULL, *p2 = NULL;
    int i = 0,j,Lenth;
    while(lists[i] == NULL && i < listsLen){
        i++;
    }
    p1 = lists[i];
    if(i != listsLen - 1){
        for(j = i + 1;j < listsLen;j++){
            p2 = lists[j];
            Lenth = lenth(p1,p2);
            mergeSort(p1, p2, Lenth);
        }
        return p1;
    }else{
        return p1;
    }
        
}


发表于 2024-04-06 14:07:17 回复(0)
C
张远鹏头像 张远鹏
/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */
struct ListNode* InsertNode(struct ListNode* headNode,struct ListNode* insertedNode)
{
    struct ListNode *previous_node=NULL,*current_node=headNode,*p=NULL;
    if(headNode==NULL)
        return insertedNode;
    if(insertedNode==NULL)
        return headNode;
    while(current_node)
    {
        if(insertedNode->val<current_node->val)
        {
            break;
        }
        previous_node = current_node;
        current_node = previous_node->next;
    }

    if(previous_node==NULL&&current_node==headNode)
    {
        insertedNode->next = current_node;
        p = insertedNode;
    }
    else if(previous_node!=NULL&&current_node==NULL)
    {
        previous_node->next = insertedNode;
        p = headNode;
    }
    else {
        insertedNode->next = current_node;
        previous_node->next = insertedNode;
        p = headNode;
    }
    return p;
}

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param lists ListNode类一维数组
 * @param listsLen int lists数组长度
 * @return ListNode类
 */
struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) {
    // write code here
    struct ListNode *HeadNode=NULL, *current_node=NULL,*p=NULL;
    int i = 0;
    if(listsLen == 0)
    {
        return NULL;
    }

    HeadNode = lists[0];
   
    for(i=1;i<listsLen;i++)
    {
        current_node = lists[i];
        while(current_node)
        {
            p = current_node;
            current_node = current_node->next;
            p->next=NULL;
            HeadNode = InsertNode(HeadNode,p);

        }
    }
return HeadNode;
}
编辑于 2024-03-25 17:28:10 回复(0)
C
一个优雅的程序猿头像 一个优雅的程序猿 
 void AddListNode(struct ListNode** head, int m, int val) {
    struct ListNode *NewNode,*p1;
    
    NewNode = (struct ListNode *)malloc(sizeof(struct ListNode));
    NewNode->val = val;
    if(!m) {
        NewNode->next = *head;
        *head = NewNode;
        return;
    }

    p1 = *head;
    while((--m>0)&&(p1->next!=NULL)) 
        p1 = p1->next;
    {
        struct ListNode *buffer;
        buffer = p1->next;
        p1->next = NewNode;
        NewNode->next = buffer;
    }
}

struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) {
    struct ListNode *res=NULL,*p1,*p2;
    
    if(!listsLen)
        return NULL;
        
    res = mergeKLists(lists, listsLen-1);
    p1 = lists[listsLen-1];

    if(p1 == NULL) 
        return res;
    if(res == NULL) 
        return p1;

    do {
        int AddLoc = 0;
        p2 = res;

        do {
            if(p1->val <= p2->val) {
                AddListNode(&res, AddLoc, p1->val);
                break;
            }
            AddLoc++;
            p2 = p2->next;
        }while(p2 != NULL);

        if(p2 == NULL) 
            AddListNode(&res, AddLoc, p1->val);

        p1 = p1->next;
    }while(p1 != NULL);

    return res;
}
这是我第一次完全自己调通的稍微复杂的递归，总结一句：特殊情况必须考虑，不然递归不通。我没有看解题思路，肯定没有官方的好，不算是最好的代码，但已经成就满满。高手解题思路才是真正的简。
发表于 2024-03-13 22:46:20 回复(0)
C
求offer的她很讲文明头像 求offer的她很讲文明
/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param lists ListNode类一维数组
 * @param listsLen int lists数组长度
 * @return ListNode类
 */
struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) {
    // write code here
    struct ListNode *pre1 = NULL;
    struct ListNode *head = NULL;
    struct ListNode *v = malloc(sizeof(struct ListNode));
    for(int i = 0 ; i < listsLen ; i++)
    {
        struct ListNode *pre2 = lists[i];
        if(pre2 == NULL)
        {
            continue;
        }
        if(head == NULL)
        {
            head = pre2;
            v->next=head;
            continue;
        }
        struct ListNode *pre3 = v;
        pre1 = v->next;
        struct ListNode *pre4 = NULL;
        while(pre1 != NULL && pre2 != NULL)
        {
            if(pre1->val >= pre2->val)
            {
                pre4 = pre2->next;
                pre3->next = pre2;
                pre2->next = pre1;
                pre3 = pre2;
                pre2 = pre4;
            }
            else
            {
                pre3 = pre1;
                pre1 = pre1->next;
            }
        }
        if(pre1 == NULL)
        {
            pre3->next = pre2;
        }
        head=v->next;
    }
    return v->next;
}
发表于 2023-09-15 20:39:14 回复(0)
C
牛客51632706号头像 牛客51632706号
struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) {
    // write code here
    struct ListNode* p1,*p2,*current,*prev;  //p1 1号链表 p2 2号链表 current当前节点 prev上一个节点
    struct ListNode result;  //实体化一个节点做首节点

    if (!lists || listsLen==0) return NULL;  //空指针和空元素直接返回

    result.next=lists[--listsLen];  //默认listsLen只有1时

    while (listsLen) {

        p1=result.next;
        p2=lists[--listsLen]; //再取一个链表给p2
        prev=&result;  //第一次赋值时，prev就是result本身

        //有空节点就继续循环再取一个链表
        if (!(p1 && p2)) {
            result.next=p1?p1:p2;
            continue;
        }  

        //实现两个节点的混插，start->
        //两个节点有一个为空了，就退出
        while (p1 && p2) {
        if (p1->val<p2->val) {
            current=p1;
            p1=p1->next;
            prev->next=current;
            prev=prev->next;
            continue;  
        }else {
            current=p2;
            p2=p2->next;
            prev->next=current;
            prev=prev->next;
        }
        }

        //退出循环后，把没空的节点放到前一个节点之后
        prev->next=p1 ? p1 : p2 ;
        //实现两个节点的混插，<-end
    }
 
    return result.next;

发表于 2023-08-02 13:00:09 回复(0)
C
小熊猫的黑眼圈头像 小熊猫的黑眼圈
/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param lists ListNode类一维数组
 * @param listsLen int lists数组长度
 * @return ListNode类
 */
static struct ListNode* Merge(struct ListNode*list1,struct ListNode*list2)
{
    struct ListNode t;
    struct ListNode* p=&t;
    p->next=NULL;
    while(list1&&list2)
    {
        if(list1->val<list2->val)
        {
            p->next=list1;
            p=list1;
            list1=list1->next;
        }
        else if(list1->val>list2->val)
        {
            p->next=list2;
            p=list2;
            list2=list2->next;
        }
        else if(list1->val==list2->val)
        {
            p->next=list1;
            p=list1;
            list1=list1->next;
            p->next=list2;
            p=list2;
            list2=list2->next;
        }
    }
    if(list1)
    {
        p->next=list1;
    }
    else if(list2)
    {
        p->next=list2;
    }

    return t.next;
}

struct ListNode* MSort(struct ListNode** lists,int left,int right)
{
    if(right>left)
    {
        struct ListNode* list1=NULL;
        struct ListNode* list2=NULL;
        int mid=left+(right-left)/2;

        list1=MSort(lists,left,mid);
        list2=MSort(lists,mid+1,right);
        return Merge(list1,list2);
    }

    return *(lists+left);
}

struct ListNode* mergeKLists(struct ListNode** lists, int listsLen )
{
    return MSort(lists,0,listsLen-1);
}
发表于 2023-07-02 17:02:20 回复(0)
C
不放弃的放鸽子能手很想熬夜头像 不放弃的放鸽子能手很想熬夜
和上题一样的思路，p q 两个序列进行归并， 归并得出的新的序列和下个序列进行归并 
#include <stdlib.h>
struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) {
    // write code here
    struct ListNode* head = NULL;
    struct ListNode* p = *lists;
    struct ListNode* t = (struct ListNode*)malloc(sizeof(struct ListNode)); //归并后序列
    head = t;
    
    for(int i = 1; i < listsLen; i++)
    {
        struct ListNode* q = lists[i];

        while (p != NULL || q != NULL)
        {
            if(p == NULL)
            {
                t->next = q;
                break;
            }
            if(q == NULL)
            {
                t->next = p;
                break;
            }

            if(p->val < q->val)
            {
                t->next = p;
                p = p->next;
                t = t->next;
            }
            else
            {
                t->next = q;
                q = q->next;
                t = t->next;
            }
        }
        p = head->next;
        t = head;
    }
    head = head->next;
    return head;
}


发表于 2023-04-01 16:26:43 回复(0)
C
帅奶哟。头像 帅奶哟。 
#include <stdlib.h>
int s[5000];

int privot(int a[], int low, int high);
void quicksort(int a[], int low, int high);

struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) {
    // write code here
    int i = 0;
    int j = 0;
    struct ListNode *p;
    //将所有链表的值赋给数组s
    for (j = 0; j < listsLen; j++){
        p = lists[j];
        while(p) {
            s[i++] = p->val;
            p = p->next;
        }
    }

    //对数组s进行快排
    quicksort(s, 0, i-1);
    
    struct ListNode *q = (struct ListNode *)malloc(sizeof(struct ListNode));
    q->next = NULL;
    p = q;

    //将排好序的值一一赋给新的链表
    for (j = 0; j < i; j++){
        struct ListNode *r = (struct ListNode *)malloc(sizeof(struct ListNode));
        r->val = s[j];
        r->next = NULL;
        p->next = r;
        p = p->next;
    }
    return q->next;
}

//划分
int privot(int a[], int low, int high) {
    int temp = a[low];
    while (low < high){
        while (low < high && a[high] >= temp) high--;
        a[low] = a[high];
        while (low < high && a[low] <= temp) low++;
        a[high] = a[low];
    }
    a[low] = temp;
    return low;
}

//快排
void quicksort(int a[], int low, int high){
    if (low < high) {
        int pri = privot(a, low, high);
        quicksort(a, low, pri-1);
        quicksort(a, pri+1, high);
    }
}

发表于 2023-03-19 16:53:57 回复(0)
C
牛客57924907号头像 牛客57924907号
struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) {
    // write code here//双指针
    if(listsLen==1||listsLen==0)
    {
        return lists[0];
    }
    if(lists[0]==NULL&&listsLen==2)
      {
        return lists[1];
      }
   int i=0,k=0;
   struct ListNode *first=NULL;
   int count=0;
   struct ListNode *cur;
   while (k!=listsLen-1)
    {
      if(lists[i]!=NULL)
      {
        first=lists[i];
        if(count==0)
         {
            cur=first;
            count ++;
         }
      }
       while(first->next!=NULL&&first!=NULL)
          {
               first=first->next;
          }
          k=i+1;
          if(lists[k]!=NULL&&first!=NULL)
            {
                first->next=lists[k];
            }
            i=k;




    }  struct ListNode *firstnode1=cur;
    struct ListNode *last=NULL;
     
     
     //利用冒泡排序将他们重新排序
     while(last!=cur->next){
      struct ListNode *pre=cur;
      struct ListNode *cur1=cur->next;
     
      while(cur1!=last)
        {  if(pre->val>cur1->val)
             {
                int temp=pre->val;
                pre->val=cur1->val;
                cur1->val=temp;
             }
            pre=pre->next;
            cur1=cur1->next;
        }  last=pre;
     }    
     return cur;
   
}
发表于 2023-03-16 22:05:43 回复(0)
C
牛客347888568号头像 牛客347888568号
很好奇，你们用递归分治不会报堆栈层级太深的问题吗？，可以使用双游标改为非递归分治，核心思想相同 
/**
 * 合并两个链表
 */
struct ListNode *mergeList(struct ListNode *left, struct ListNode *right)
{
    struct ListNode *head = malloc(sizeof(struct ListNode));
    struct ListNode *node = head;
    while (left && right)
    {
        if (left->val < right->val)
        {
            node->next = left;
            left = left->next;
        }
        else
        {
            node->next = right;
            right = right->next;
        }
        node = node->next;
    }
    node->next = left ? left : right;
    node = head->next;
    free(head);
    return node;
}
/**
 * @description 头尾链表合并到一起，更新头链表，直到只剩下一个链表
 * @param lists ListNode类一维数组
 * @param listsLen int lists数组长度
 * @return ListNode类
 */
struct ListNode *mergeKLists(struct ListNode **lists, int listsLen)
{
    // write code here
    if (listsLen <= 0) {
        return NULL;
    }
    int st = 0, ed = listsLen - 1;
    while (ed > 0)
    {
        st = 0;
        while (st < ed && ed)
        {
            lists[st] = mergeList(lists[st], lists[ed]);
            st++;
            ed--;
        }
    }
    return lists[0];
}


发表于 2023-03-08 10:51:10 回复(0)
C
lijd头像 lijd 
/**
 * 
 * @param lists ListNode类一维数组 
 * @param listsLen int lists数组长度
 * @return ListNode类
 */
struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) {
    // write code here
    struct ListNode* head = NULL;
    int i = 0;
    for(i = 0; i < listsLen; i++)
    {
        struct ListNode* ptr1 = lists[i];

        if(ptr1 == NULL)
            continue;

        if(head == NULL)
        {
            head = ptr1;
            continue;
        }
        struct ListNode* ptr2 = head, *ptr3 = NULL;

        while(ptr1 != NULL && ptr2 != NULL)
        {
            if(ptr1->val >= ptr2->val && ptr2->next != NULL && ptr1->val <= ptr2->next->val){
                ptr3 = ptr1->next;
                ptr1->next = ptr2->next;
                ptr2->next = ptr1;
                ptr1 = ptr3;

                ptr2 = ptr2->next;
            }else if(ptr1->val < ptr2->val){
                head = ptr1;
                ptr3 = ptr1->next;
                ptr1->next = ptr2;
                ptr2 = ptr1;

                ptr1 = ptr3;
            }else if(ptr2->next == NULL){
                ptr2->next = ptr1;
                break;
            }else{
                ptr2 = ptr2->next;
            }
        }

        if(ptr1 != NULL && ptr2 == NULL)
        {
            ptr2->next = ptr1;
        }
    }
    return head;
}

发表于 2023-01-10 15:46:51 回复(0)
C
菜鸟一枚_头像 菜鸟一枚_
我运用的选择排序的思想，主要是先将两个合并，成为一个有序的，然后再将下一个链表假如排好的的链表，直到结束，得到一个有序的链表；
struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) {
    // write code here
    int j=listsLen;
    for(int i=0;i<listsLen;i++)
    {
        if(lists[i]==NULL)
            j--; 
    }
    if(j==0)
        return *lists;
    if(j==1)
    {
        for(int i=0;i<listsLen;i++)
        {
            if(lists[i]!=NULL)
                return lists[i];
        }
    }
    struct ListNode* head=(struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode*cur;
    struct ListNode*pk,*pi;
    int k=0;int i=1;
    while(listsLen>1)
    {
        cur=head;
        pk=lists[k];
        pi=lists[i];
        while(pk&&pi)
        {
            if(pk->val<=pi->val)
            {
                cur->next=pk;
                pk=pk->next;
            }
            else{
                cur->next=pi;
                pi=pi->next;
            }
            cur=cur->next;
        }
        if(pk)
        {
            cur->next=pk;
        }
        if(pi)
        {
            cur->next=pi;
        }   
        if(head->next==lists[k])
        {
            i=i+1;
        }
        if(head->next==lists[i])
        {
            k=i;
            i=i+1;
        }
        listsLen--;
    }
    return head->next;

}
发表于 2022-11-22 15:15:17 回复(0)
C
牛客336312983号头像 牛客336312983号 
struct ListNode* mergeKLists(struct ListNode** lists, int listsLen) {
    // write code here
    if (listsLen == 1)
        return lists[0];

    struct ListNode* newNodeBegin[2002];
    struct ListNode* newNodeEnd[2002];
    
    struct ListNode* node;
    struct ListNode* nodeNext;

    for (int i = 0; i < listsLen; ++i)
    {
        node = lists[i];
        while (node != NULL)
        {
            nodeNext = node->next;
            node->next = NULL;
            if (newNodeBegin[node->val + 1000] == NULL)
            {
                newNodeBegin[node->val + 1000] = node;
                newNodeEnd[node->val + 1000] = node;
            }
            else
            {
                node->next = newNodeBegin[node->val + 1000];
                newNodeBegin[node->val + 1000] = node;
            }
            node = nodeNext;
        }
       
    }

    node = NULL;
    nodeNext = NULL;
    for (int i = 0; i <= 2000; ++i)
    {
        if (newNodeBegin[i] != NULL)
        {
            if (node == NULL)
            {
                node = newNodeBegin[i];
                nodeNext = newNodeEnd[i];
            }
            else
            {
                nodeNext->next = newNodeBegin[i];
                nodeNext = newNodeEnd[i];
            }
        }
    }

    return node;
    
}
//简单粗暴，题目给定了val的取值范围，直接弄一个2000的数组。先把每个val值相同节点的串起来。然后重小到大循环再链接一次
//这样 你甚至可以传入不是排好序的链表
发表于 2022-11-03 16:40:25 回复(0)
C
取nm名字全被取了头像 取nm名字全被取了 
struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) 
{
    int i = 0;
    struct ListNode *newhead = lists[0];
    int flag = 1;
    if(!listsLen)
    {
        return lists[0];
    }
    while(i != listsLen)
    {
        struct ListNode *p;
        if(lists[i])
        {
            if(flag)
            {
                newhead = lists[i];
                flag = 0;
            }
            if(i == listsLen-1)
            break;
            p = lists[i];
            while(p->next)
            {
                p = p->next;
            }
            while(!lists[++i])
            {
                if(i == listsLen-1)
                {
                    break;
                }
            }
            p->next = lists[i];
        } 
        else
        {
            i++;
        }
    }
    struct ListNode *q = NULL;
    struct ListNode *temp;
    int val;
    struct ListNode *p = newhead;
    while(p)
    {
        temp = p;
        q = p;
        while(q)
        {
            if(temp->val > q->val)
            {
                temp = q;
            }
            q = q->next;
        }
        val = p->val;
        p->val = temp->val;
        temp->val = val;
        p = p->next;
    }
    return newhead;
    // write code here
}

发表于 2022-11-02 21:19:35 回复(0)
C
0wning头像 0wning
使用递归将链表两两融合
/**
 *
 * @param pHead1 ListNode类
 * @param pHead2 ListNode类
 * @return ListNode类
 */
struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    // write code here
    // 每次从链表中选择较小的那一个连接到链表中
    struct ListNode* l1 = pHead1;
    struct ListNode* l2 = pHead2;
    if(l1 == NULL && l2 == NULL) {
        return NULL;
    }
    if(l1 == NULL && l2) {
        return l2;
    }
    if(l1 && l2 == NULL) {
        return l1;
    }
    if(l1->val < l2->val) {
        l1->next = Merge(l1->next, l2); // 递归链接后续最小值
        return l1;
    }else {
        l2->next = Merge(l1, l2->next); // 递归链接后续最小值
        return l2;
    }
}
/**
 * 
 * @param lists ListNode类一维数组 
 * @param listsLen int lists数组长度
 * @return ListNode类
 */
struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) {
    // write code here
    if(listsLen == 0) { // 数组为空
        return NULL;
    }
    if(listsLen ==1) { // 只有一个元素
        return lists[0];
    }
    if(listsLen == 2) { // 两个元素，直接融合
        return Merge(lists[0], lists[1]);
    }

    struct ListNode* res = lists[0];
    // 将链表两两融合 需要融合 n-1 次
    for(int i=0;i!=listsLen-1;++i){ // 到这里数组至少三个元素，至少2次融合
        res = Merge(res, lists[i+1]); // 递归融合
    }
    return res;
}
发表于 2022-10-21 20:33:05 回复(0)
C
冬xur头像 冬xur 
int    CheckPHead(struct ListNode** lists,int listsLen);//检查是否只有一个头节点不为0

struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) {
    // write code here
    struct ListNode* nh=(struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* sh=nh;
    struct ListNode* lmin=0;
    
    while(CheckPHead(lists,listsLen)){
        int min=1001;//j最小值的索引
        for(int i=0;i<listsLen;i++){    //找出最小值
            if(lists[i]!=0){
                if(min>lists[i]->val){
                    min=lists[i]->val;
                }
            }
        }
        for(int i=0;i<listsLen;i++){    //链接
            if(lists[i]!=0){
                if(lists[i]->val==min){
                    nh->next=lists[i];nh=lists[i];
                    lists[i]=lists[i]->next;
                }
            }
        }
    }
    
    for(int i=0;i<listsLen;i++){    //链接最长的结点
        if(lists[i]!=0){
            nh->next=lists[i];
        }
    }
    
    return sh->next;
}

int    CheckPHead(struct ListNode** lists,int listsLen){
        int count=0;
        for(int i=0;i<listsLen;i++){
            if(lists[i]!=0){
                count++;
            }
        }
        if(count<=1){
            return 0;
        }else{
            return 1;
        }
}

发表于 2022-08-18 20:44:29 回复(0)
C
无名氏201908021431738头像 无名氏201908021431738 
C语言实现方法：
基本思路：归并排序法，递归排序
struct ListNode* sort(struct ListNode* l, struct ListNode* r)
{
    struct ListNode head = {0};
    struct ListNode* cur = &head;
    
    while (l != NULL && r != NULL) {
        if (l->val <= r->val) {
            cur->next = l;
            cur = cur->next;
            l = l->next;
        } else {
            cur->next = r;
            cur = cur->next;
            r = r->next;
        }
    }
    if (l != NULL) {
        cur->next = l;
    }
    if (r != NULL) {
        cur->next = r;
    }
    
    return head.next;
}

struct ListNode* mergesort(struct ListNode** lists, int left, int right)
{
    int mid = 0;
    struct ListNode *l = NULL, *r = NULL;
    if (left < right) {
        mid = (left + right) / 2;
        
        l = mergesort(lists, left, mid);
        
        r = mergesort(lists, mid + 1, right);
        
        return sort(l, r);
    } else {
        return lists[left];
    }
}

struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) {

    return mergesort(lists, 0, listsLen - 1);

}

发表于 2022-07-16 14:41:12 回复(0)
提交观点

问题信息

分治 链表 堆
难度：
25条回答 26661浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号