首页 > 试题广场 >

合并k个已排序的链表

[编程题]合并k个已排序的链表
  • 热度指数：214285 时间限制：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
牛客712087098号头像 牛客712087098号 
struct ListNode * get_next_min_node(struct ListNode **pNextTbl, int listsLen, int *list_left) {
    int min = -1;
    int cnt = listsLen;
    struct ListNode *pNode = NULL;

    for (int i = 0; i < listsLen; i++) {
        if (!pNextTbl[i]) {
            cnt--;
            continue;
        }

        if (min == -1) {
            min = i;
        } else {
            min = (pNextTbl[i]->val > pNextTbl[min]->val) ? min : i;
        }
    }

    if (min == -1) {
        return NULL;
    }

    *list_left = cnt;
    pNode = pNextTbl[min];
    pNextTbl[min] = pNextTbl[min]->next;
    return pNode;
}


struct ListNode* mergeKLists(struct ListNode** lists, int listsLen) {
    // write code here
    struct ListNode **pNextTbl = NULL;
    struct ListNode *pList = NULL;
    struct ListNode *pTmp= NULL;
    struct ListNode *pListHead = NULL;
    int list_left = 0;

    if (!lists) {
        return NULL;
    }

    pNextTbl = malloc(sizeof(struct ListNode *)*listsLen);
    if (!pNextTbl) {
        return NULL;
    }

    memset(pNextTbl, 0, sizeof(struct ListNode *)*listsLen);
    for (int i = 0; i < listsLen; i++) {
        if (lists[i]) {
            list_left++;
            pNextTbl[i] = lists[i];
        }
    }

    while ((pTmp = get_next_min_node(pNextTbl, listsLen, &list_left)) != NULL) {
        if (pList) {
            pList->next = pTmp;
        } else {
            pListHead = pTmp;
        }
        pList = pTmp;
    };

    free(pNextTbl);

    return pListHead;
}

发表于 2025-03-25 17:46:34 回复(0)
C
牛客357419673号头像 牛客357419673号
struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) {
    // write code here
    struct ListNode head = {0, NULL};
    struct ListNode* phead = &head;

    while (listsLen > 0) {
        struct ListNode** min = NULL;

        for (int i = 0; i < listsLen; i++) {
            if (!lists[i] && i < listsLen) {
                //printf("switch %d<-%d, leftLen:%d\n", i, listsLen-1, listsLen - 1);
                lists[i--] = lists[listsLen - 1];
                listsLen--;
                continue;
            }

            if (min == NULL || lists[i]->val < (*min)->val) {
                min = &lists[i];
            }
        }

        if (listsLen <= 0 || min == NULL) {
            break;
        }

        phead->next = *min;
        phead = phead->next;

        *min = (*min)->next;
    }

    return head.next;
}
发表于 2025-01-10 20:25:08 回复(0)
C
牛客463694086号头像 牛客463694086号
// 比较每个list最前面的node value，找到val最小的，合并成新的list即可
struct ListNode* findNode(struct ListNode **lists, int listsLen)
{
    struct ListNode *next = NULL;
    int i, tmp = 0;

    for (i = 0; i < listsLen; i++) {
        if (lists[i]) {
            if (!next) {
                next = lists[i];
                tmp = i;
            }

            if (next->val > lists[i]->val) {
                next = lists[i];
                tmp = i;
            }
        }
    }

    if (lists[tmp]) {
        lists[tmp] = lists[tmp]->next;
    }
   
    return next;
}

struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) {
    struct ListNode prev, *head, *tmp;

    prev.next = NULL;
    tmp = &prev;
    while (1) {
        tmp->next = findNode(lists, listsLen);
        if (!tmp->next) {
            break;
        }
        tmp = tmp->next;
    }

    return prev.next;
}
发表于 2024-11-25 15:55:47 回复(0)
C
木子小宇头像 木子小宇
struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) {
    // write code here
    if(listsLen==0) return NULL;
    struct ListNode P;
    struct ListNode* p=&P;
    p->next=NULL;
    int min=1000;
    while(1)
    {
        int min_n=0;
        for(int i=0,n=0; i<listsLen; i++)
        {
            if(lists[i]==NULL)
            {
                n++;
                if(n==listsLen) return P.next;
                continue;
            }
            if(min>=lists[i]->val)
            {
                min=lists[i]->val;
                min_n=i;
            }
        }
        p->next=lists[min_n];
        p=p->next;
        lists[min_n]=lists[min_n]->next;
        min=1000;
    }
}
发表于 2024-09-05 12:51:30 回复(0)
C
湫湫宁头像 湫湫宁 
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param lists ListNode类一维数组 
 * @param listsLen int lists数组长度
 * @return ListNode类
 */
struct ListNode* merge(struct ListNode* p1, struct ListNode* p2)
{
    //合并函数，合并两链表
    struct ListNode* mhead = (struct ListNode*)malloc(sizeof(struct ListNode));
    mhead->next = p1;
    struct ListNode* cur = mhead;
    
    while(p1 && p2)
    {
        if(p1->val <= p2->val)
        {
            cur->next = p1;
            p1 = p1->next;
        }
        else
        {
            cur->next = p2;
            p2 = p2->next;
        }
        cur = cur->next;
    }
    if(p1)
    {
        cur->next = p1;
    }
    if(p2)
    {
        cur->next = p2;
    }
    return mhead->next;
}
struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) {
    // write code here
    struct ListNode* mhead = NULL;
    while(listsLen--)
    {
        mhead = merge(mhead, lists[listsLen]);
    }
    return mhead;
}
在上题基础上加个循环累加就可。
发表于 2024-08-16 11:55:46 回复(0)
C
terirx头像 terirx 
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param lists ListNode类一维数组 
 * @param listsLen int lists数组长度
 * @return ListNode类
 */

struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ){
    struct ListNode* pHead =(struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* beginHead = NULL;
    int min=1001, minnum=5001;
    int endflag = 0;
    for(int i=0; i<listsLen; i++)
    {
        if(lists[i] == NULL)
        continue;
        else if(lists[i] -> val < min)
        {
            min = lists[i] -> val;
            minnum = i;
        }
    }
    if(minnum == 5001) return NULL;
    beginHead = lists[minnum];
    pHead = lists[minnum];
    lists[minnum] = lists[minnum] -> next;
    min = 1001;
    minnum = 5001;
    while(endflag == 0)
    {
        //当链表为空的时候再取链表指针中的值的时候会报错，所以要提前把边界取出来
        for(int i=0; i<listsLen; i++)
        {
            if(lists[i] == NULL)
            continue;
            else if(lists[i] -> val < min)
            {
                min = lists[i] -> val;
                minnum = i;
            }
        }
        if(min == 1001 && minnum ==5001)
        endflag = 1;
        else 
        {
            pHead -> next = lists[minnum];
            pHead = lists[minnum];
            lists[minnum] = lists[minnum] -> next;
            min = 1001;
            minnum = 5001;
        }
    // write code here
    }
        return beginHead;
}

发表于 2024-08-07 16:24:45 回复(0)
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 回复(1)
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)
提交观点

问题信息

分治 链表 堆
难度：
31条回答 29749浏览

热门推荐

通过挑战的用户

查看代码

相关试题

合并k个已排序的链表

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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