精华内容
下载资源
问答
  • 一、题目要求:将K个有序链表合并为一个有序链表二、实现方法:方法一:利用最小堆方法用一个大小为K的最小堆(用优先队列+自定义降序实现)(优先队列就是大顶堆,队头元素最大,自定义为降序后,就变成小顶堆,队头...

    一、题目要求:

    将K个有序链表合并为一个有序链表

    二、实现方法:

    方法一:利用最小堆方法

    用一个大小为K的最小堆(用优先队列+自定义降序实现)(优先队列就是大顶堆,队头元素最大,自定义为降序后,就变成小顶堆,队头元素最小),先把K个链表的头结点放入堆中,每次取堆顶元素,然后将堆顶元素所在链表的下一个结点加入堆中。

    d2dfd1edb4654f958100f4f2481dfd6a.jpg

    be069ab2dba34c058e2a0c5564a3c337.jpg

    整体测试代码:

    #include

    #include

    #include

    #include

    #include // std::greater

    using namespace std;

    struct ListNode

    {

    int val;

    ListNode* next;

    };

    struct cmp

    {

    bool operator()(ListNode* a, ListNode* b)

    {

    return a->val > b->val;

    }

    };

    //方法一:利用最小堆方法

    //用一个大小为K的最小堆(用优先队列+自定义降序实现)(优先队列就是大顶堆,队头元素最大,自定义为降序后,就变成小顶堆,队头元素最小),

    //先把K个链表的头结点放入堆中,每次取堆顶元素,然后将堆顶元素所在链表的下一个结点加入堆中。

    ListNode* mergeKLists2(vector lists)

    {

    if (lists.size() == 0) return NULL;

    priority_queue, cmp> heap;

    for (int i = 0; i < lists.size(); ++i)

    {

    heap.push(lists[i]);

    }

    ListNode* newHead=NULL;

    ListNode* p=NULL;

    ListNode* q=NULL;

    while (!heap.empty())

    {

    q = heap.top();

    heap.pop();

    if (q->next != NULL) heap.push(q->next);

    if (newHead == NULL)

    {

    newHead = q;

    p = q;

    }

    else

    {

    p->next = q;

    p = p->next;

    }

    }

    return newHead;

    }

    ListNode* CreateListNode(int value)

    {

    ListNode* pNode = new ListNode();

    pNode->val = value;

    pNode->next = NULL;

    return pNode;

    }

    void DestroyList(ListNode* pHead)

    {

    ListNode* pNode = pHead;

    while (pNode != NULL)

    {

    pHead = pHead->next;

    delete pNode;

    pNode = pHead;

    }

    }

    void ConnectListNodes(ListNode* pCurrent, ListNode* pNext)

    {

    if (pCurrent == NULL)

    {

    printf("Error to connect two nodes.\\n");

    exit(1);

    }

    pCurrent->next = pNext;

    }

    int main()

    {

    vector lists;

    ListNode* pNode1 = CreateListNode(1);

    ListNode* pNode2 = CreateListNode(2);

    ListNode* pNode3 = CreateListNode(3);

    ListNode* pNode4 = CreateListNode(4);

    ListNode* pNode5 = CreateListNode(2);

    ListNode* pNode6 = CreateListNode(3);

    ListNode* pNode7 = CreateListNode(4);

    ListNode* pNode8 = CreateListNode(5);

    ListNode* pNode9 = CreateListNode(6);

    ListNode* pNode10 = CreateListNode(7);

    ListNode* pNode11 = CreateListNode(8);

    ListNode* pNode12 = CreateListNode(9);

    ConnectListNodes(pNode1, pNode2);

    ConnectListNodes(pNode2, pNode3);

    ConnectListNodes(pNode3, pNode4);

    ConnectListNodes(pNode5, pNode6);

    ConnectListNodes(pNode6, pNode7);

    ConnectListNodes(pNode7, pNode8);

    ConnectListNodes(pNode9, pNode10);

    ConnectListNodes(pNode10, pNode11);

    ConnectListNodes(pNode11, pNode12);

    ListNode* L1 = pNode1;

    ListNode* L2 = pNode5;

    ListNode* L3 = pNode9;

    cout << "链表l1: ";

    while (L1)

    {

    cout << L1->val << " ";

    L1 = L1->next;

    }

    cout << endl;

    cout << "链表l2: ";

    while (L2)

    {

    cout << L2->val << " ";

    L2 = L2->next;

    }

    cout << endl;

    cout << "链表l3: ";

    while (L3)

    {

    cout << L3->val << " ";

    L3 = L3->next;

    }

    cout << endl;

    lists.push_back(pNode1);

    lists.push_back(pNode5);

    lists.push_back(pNode9);

    ListNode* res = mergeKLists2(lists);

    cout << "合并后链表: ";

    while (res)

    {

    cout << res->val << " ";

    res = res->next;

    }

    cout << endl;

    system("pause");

    DestroyList(res);

    return 0;

    }

    ef3d39f8f77d443fa89a885e3528da1b.jpg

    方法二:分治法

    利用归并排序的思想,利用递归和分治法将链表数组划分成为越来越小的半链表数组,再对半链表数组排序,最后再用递归步骤将排好序的半链表数组合并成为越来越大的有序链表。

    541151de0b614876a23903407ce929bf.jpg

    acd938bc42a84e3d8a7bf5f03490313a.jpg

    整体测试代码:

    #include

    #include

    using namespace std;

    struct ListNode

    {

    int val;

    ListNode* next;

    };

    //方法二:分治法

    //利用归并排序的思想,利用递归和分治法将链表数组划分成为越来越小的半链表数组,

    //再对半链表数组排序,最后再用递归步骤将排好序的半链表数组合并成为越来越大的有序链表

    ListNode* mergeKLists(vector lists, int K)

    {

    return mergeLists(lists, 0, K);

    }

    ListNode* mergeLists(vector listNodes, int low, int high)

    {

    if (low == high) return NULL;

    if (high - low == 1) return listNodes[low];

    if (high - low == 2) return merge2(listNodes[low], listNodes[high - 1]);

    int mid = (high + low) / 2;

    ListNode* a = mergeLists(listNodes, low, mid);

    ListNode* b = mergeLists(listNodes, mid, high);

    return merge2(a, b);

    }

    ListNode* merge2(ListNode* L1, ListNode* L2)

    {

    if (L1 == NULL && L2 == NULL) return NULL;

    else if (L1 == NULL) return L2;

    else if (L2 == NULL) return L1;

    ListNode* newHead = NULL;

    ListNode* p = NULL;

    if (L1->val < L2->val){ newHead = L1; p = L1; L1 = L1->next; }

    else{ newHead = L2; p = L2; L2 = L2->next; }

    while (L1 != NULL && L2 != NULL)

    {

    if (L1->val < L2->val)

    {

    p->next = L1;

    L1 = L1->next;

    }

    else

    {

    p->next = L2;

    L2 = L2->next;

    }

    p = p->next;

    }

    p->next = L1 ? L1 : L2;

    return newHead;

    }

    ListNode* CreateListNode(int value)

    {

    ListNode* pNode = new ListNode();

    pNode->val = value;

    pNode->next = NULL;

    return pNode;

    }

    void DestroyList(ListNode* pHead)

    {

    ListNode* pNode = pHead;

    while (pNode != NULL)

    {

    pHead = pHead->next;

    delete pNode;

    pNode = pHead;

    }

    }

    void ConnectListNodes(ListNode* pCurrent, ListNode* pNext)

    {

    if (pCurrent == NULL)

    {

    printf("Error to connect two nodes.\\n");

    exit(1);

    }

    pCurrent->next = pNext;

    }

    int main()

    {

    vector lists;

    ListNode* pNode1 = CreateListNode(1);

    ListNode* pNode2 = CreateListNode(2);

    ListNode* pNode3 = CreateListNode(3);

    ListNode* pNode4 = CreateListNode(4);

    ListNode* pNode5 = CreateListNode(2);

    ListNode* pNode6 = CreateListNode(3);

    ListNode* pNode7 = CreateListNode(4);

    ListNode* pNode8 = CreateListNode(5);

    ListNode* pNode9 = CreateListNode(6);

    ListNode* pNode10 = CreateListNode(7);

    ListNode* pNode11 = CreateListNode(8);

    ListNode* pNode12 = CreateListNode(9);

    ConnectListNodes(pNode1, pNode2);

    ConnectListNodes(pNode2, pNode3);

    ConnectListNodes(pNode3, pNode4);

    ConnectListNodes(pNode5, pNode6);

    ConnectListNodes(pNode6, pNode7);

    ConnectListNodes(pNode7, pNode8);

    ConnectListNodes(pNode9, pNode10);

    ConnectListNodes(pNode10, pNode11);

    ConnectListNodes(pNode11, pNode12);

    ListNode* L1 = pNode1;

    ListNode* L2 = pNode5;

    ListNode* L3 = pNode9;

    cout << "链表l1: ";

    while (L1)

    {

    cout << L1->val << " ";

    L1 = L1->next;

    }

    cout << endl;

    cout << "链表l2: ";

    while (L2)

    {

    cout << L2->val << " ";

    L2 = L2->next;

    }

    cout << endl;

    cout << "链表l3: ";

    while (L3)

    {

    cout << L3->val << " ";

    L3 = L3->next;

    }

    cout << endl;

    lists.push_back(pNode1);

    lists.push_back(pNode5);

    lists.push_back(pNode9);

    ListNode* res = mergeKLists(lists, 3);

    cout << "合并后链表: ";

    while (res)

    {

    cout << res->val << " ";

    res = res->next;

    }

    cout << endl;

    system("pause");

    DestroyList(res);

    return 0;

    }

    815b6466064f4b95b6dbeb5034e32ee0.jpg

    展开全文
  • 本篇文章通过代码示例介绍一下使用c语言合并个有序链表的方法。有一定的参考价值,有需要的朋友可以参考一下,希望对大家有所帮助。教程推荐:《c语言教程视频》c语言实现两个有序链表的合并现有两有序单链表,...

    本篇文章通过代码示例介绍一下使用c语言合并两个有序链表的方法。有一定的参考价值,有需要的朋友可以参考一下,希望对大家有所帮助。

    7182196577ee68dde56dea15244dab06.png

    教程推荐:《c语言教程视频》

    c语言实现两个有序链表的合并

    现有两个有序单链表,通过代码实现将两个单链表合并为一个有序的新表,要求使用旧表的空间,不能新分配内存#include #include typedef struct List{

    int a;

    struct List *next;}list;void newList(list *l){

    //初始化头节点

    l->next = NULL;}void setList(list * l){

    //建立链表

    int i = 1;

    int j;

    while (i)

    {

    scanf_s("%d", &j);

    if (j == -1)

    {

    i = 0;

    }

    else

    {

    list *l1 = (list *)malloc(sizeof(list));//为新的结点分派内存

    l1->a = j;//储存数据

    /*

    将最后结点的next区域指向新结点

    将新结点的next区域指向设置为空

    */

    l->next = l1;

    l1->next = NULL;

    l = l->next;

    }

    }}void printfList(list *l){

    printf("该链表内容为:\n");

    while (l->next)

    {

    printf("%d\t", l->next->a);

    l = l->next;

    }

    printf("\n");}list *add(list *LA, list *LB){

    //记录两个链表的头结点

    list *la=LA;

    list *l = LA;

    list *lb = LB;

    //移动指针

    LA = LA->next;

    LB = LB->next;

    la->next = NULL;

    while (LA!=NULL&&LB!=NULL)

    {

    /*

    将两个结点的数据进行比较,数据较小的结点接在头结点后面,

    */

    if (LA->a < LB->a)

    {

    la->next = LA;

    la = LA;

    LA = LA->next;

    }

    else

    {

    la->next = LB;

    la = LB;

    LB = LB->next;

    }

    }

    //若其中一个链表的结点已经全接在新表中则将另一个链表的剩余结点接在新表的后面

    if (LA)

    {

    la->next = LA;

    }

    if(LB)

    {

    la->next = LB;

    }

    free(lb);

    return l;}int main(){

    //为结点分配内存

    list *LA = (list *)malloc(sizeof(list));

    list *LB = (list *)malloc(sizeof(list));

    //初始化结点

    newList(LA);

    newList(LB);

    //建立链表

    setList(LA);

    setList(LB);

    //输出链表的内容

    printf("LA的数据:\n");

    printfList(LA);

    printf("LB的数据:\n");

    printfList(LB);

    list *LC = add(LA, LB);

    //输出合并后的新表

    printfList(LC);

    system("pause");

    return 0;}

    6475c2a7d2f3b355b02e2c9a64b57b12.png

    更多编程相关知识,请访问:编程入门!!

    展开全文
  • leetcode第一题,两有序链表合并。 基本思想:每次比较两链表的数,p1链表小于或等于p2的时候,插入到新的链表newList中去。这样就能实现了,那么如果是两无序链表呢,比较直接的办法就是先分别排序,但是这样...

    概述

    leetcode第一题,两有序链表合并。

    基本思想:每次比较两个链表的数,p1链表小于或等于p2的时候,插入到新的链表newList中去。这样就能实现了,那么如果是两个无序链表呢,比较直接的办法就是先分别排序,但是这样肯定在效率上不行,那么怎么实现呢?

    题目

    将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

    示例 1:
    输入:l1 = [1,2,4], l2 = [1,3,4]
    输出:[1,1,2,3,4,4]

    示例 2:

    输入:l1 = [], l2 = []
    输出:[]

    示例 3:

    输入:l1 = [], l2 = [0]
    输出:[0]
     

    算法代码 

    struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
        typedef struct ListNode Node;
        Node *p1 = l1;
        Node *p2 = l2;
        Node *head = NULL;
        Node *newPList = NULL;
    
        if (l1 != NULL && l2 != NULL)   
    	{
    		return l1 == NULL?l2:l1;
    	}
        while(p1!=NULL || p2!=NULL){
            if(p1->val<=p2->val){
                if(newPList){
                    newPList = p1;
                }
                else{
                    head = p1;
                }
                p1 = p1->next;
            }
            else{
                if(newPList){
                    newPList = p2;
                }
                else{
                    head = p2;
                }
                p2 = p2->next;
            }
            newPList = newPList->next;
        }
        return newPList;
    }
    

    参考

    leetcode

    展开全文
  • C语言合并个有序链表的方法:拼接指定的两个有序链表的所有节点即可。例如两个有序链表分别为【1->2->4】和【1->3->4】,合并后的有序链表为【1->1...

    C语言合并两个有序链表的方法:拼接指定的两个有序链表的所有节点即可。例如两个有序链表分别为【1->2->4】和【1->3->4】,合并后的有序链表为【1->1->2->3->4->4】。

    具体方法:

    将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

    输入:

    1->2->4, 1->3->4

    输出:

    1->1->2->3->4->4

    分析:两个链表为有序链表,所以依次遍历两个链表比较大小即可。

    代码实现:

    /**

     * Definition for singly-linked list.

     * struct ListNode {

     *     int val;

     *     struct ListNode *next;

     * };

     */

    struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){

        if(l1==NULL){

            return l2;

        }

        if(l2==NULL){

            return l1;

        }

        struct ListNode *l = (struct ListNode*)malloc(sizeof(struct ListNode));

        l->next = NULL;

        struct ListNode *list1 = l1;

        struct ListNode *list2 = l2;

        if(l1->valval){

            l->val=l1->val;

            if(list1->next==NULL){

                l->next=list2;

                return l;

            }

            list1=list1->next;

        }else{

            l->val=l2->val;

            if(list2->next==NULL){

                l->next=list1;

                return l;

            }

            list2=list2->next;

        }

        struct ListNode *list = l;

        while(list1->next!=NULL&&list2->next!=NULL){

            if(list1->val<=list2->val){

                struct ListNode *body = (struct ListNode *)malloc(sizeof(struct ListNode));

                body->val = list1->val;

                body->next = NULL;

                list->next = body;

                list = list->next;

                list1 = list1->next;

            }else{

                struct ListNode *body = (struct ListNode*)malloc(sizeof(struct ListNode));

                body->val=list2->val;

                body->next=NULL;

                list->next=body;

                list=list->next;

                list2=list2->next;

            }

        }

        if(list1->next==NULL){

            while(list2->next!=NULL){

                if(list1->val<=list2->val){

                    list->next = list1;

                    list = list->next;

                    list->next=list2;

                    return l;

                }else{

                    struct ListNode *body = (struct ListNode*)malloc(sizeof(struct ListNode));

                    body->val=list2->val;

                    body->next=NULL;

                    list->next=body;

                    list=list->next;

                    list2=list2->next;

                }

            }

        }else{

            while(list1->next!=NULL){

                if(list2->val<=list1->val){

                    list->next=list2;

                    list=list->next;

                    list->next=list1;

                    return l;

                }else{

                    struct ListNode *body = (struct ListNode*)malloc(sizeof(struct ListNode));

                    body->val=list1->val;

                    body->next=NULL;

                    list->next=body;

                    list=list->next;

                    list1=list1->next;

                }

            }

        }

        if(list1->next==NULL&&list2->next==NULL){

            if(list1->val<=list2->val){

                list->next = list1;

                list=list->next;

                list->next=list2;

            }else{

                list->next=list2;

                list=list->next;

                list->next=list1;

            }

        }

        return l;

    }

    声明:

    本文于网络整理,版权归原作者所有,如来源信息有误或侵犯权益,请联系我们删除或授权事宜。


    展开全文
  • 合并个有序链表 将两升序链表合并为一新的 升序 链表并返回。新链表是通过拼接给定的两链表的所有节点组成的。 示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4 C 思想:...
  • 合并个有序链表C语言

    千次阅读 2019-04-26 18:54:12
    将两个有序链表合并为一新的有序链表并返回。新链表是通过拼接给定的两链表的所有节点组成的。 示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4 解决思路 1.排列顺序为由小到...
  • 这次来写一下 LeetCode 的第 21 题,合并个有序链表。 题目描述 题目直接从 LeetCode 上截图过来,题目如下: 上面的题就是 合并个有序链表 题目的截图,同时 LeetCode 会根据选择的语言给出了一...
  • 有两种方式,第一种是将两个链表合并为一新的链表。第二种方式是将一个链表合并到另一个链表上。 #include<stdio.h> #include <stdlib.h> typedef struct node { int val; struct node *next; }...
  • 今天白天没课 自己还是早早的就过来了 上午刷了一道题之后 还是一如既往的看了一场我詹的比赛 下午上党课 晚上在实验室做应用数理统计的题目时 ...明天早上起来吃一梅干菜和鱼香肉丝的包子 对我来说就又是新...
  • 将两升序链表合并为一新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1: 输入:l1 = [1,2,4], l2 = [1,3,4] 输出:[1,1,2,3,4,4] 示例 2: 输入:l1 = [], l2 = [] 输出:[] ...
  • 方法一:每两个链表递归合并合并(lists.length-1)次 链表数据结构 #include<stdio.h> #include<stdlib.h> #include<malloc.h> struct ListNode { int val; struct ListNode *next; }; ...
  • 21. 合并个有序链表 将两升序链表合并为一新的升序链表并返回。新链表是通过拼接给定的两链表的所有节点组成的。 示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4 /** *...
  • 初始条件下有两个有序链表(假设都是递增顺序),则可以采用单链表的尾插法建立链表。不需要在第一链表的基础上动态申请空间,也不需要对第二链表的结点做删除操作。因为第二链表的每一结点都是动态申请过来...
  • 本题要求实现一函数,将两个链表表示的递增整数序列合并为一非递减的整数序列。 //函数接口定义: List Merge( List L1, List L2 ); //其中List结构定义如下: typedef struct Node *PtrToNode; struct Node { ...
  • 个有序链表序列的合并,已知两非降序链表序列S1与S2,设计函数构造出S1与S2的并集新非降序链表S3。
  • 合并个有序链表C语言) 数据结构-链表:算法与数据结构参考 题目: 将两个有序链表合并为一新的有序链表并返回。新链表是通过拼接给定的两链表的所有节点组成的。 示例: 输入:1->2->4, 1->3->...
  • 21. 合并个有序链表 Description 将两个有序链表合并为一新的有序链表并返回。新链表是通过拼接给定的两链表的所有节点组成的。 示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3->...
  • 将两个有序链表合并为一链表任然有序,两链表都是从大到小或者从小到大。 方法: 1.将两链表连起来,对所有元素进行排序。 2.因为两链表的长度可能不同,则将两链表相同长度的一部分进行排序,将较长链表的...
  • 从txt文件中读取5 4 2 3 1 10 6 8 7 9 到数组中,建立了两递增排序的双向链表,内容分别为 1 2 3 4 5和6 7 8 9 10,现在想将两个链表合并输出一递增的双向链表,输出时少了1和6 两数字,双向链表创建时没有...
  • 合并个链表: ------ 链表a:3 -> 4 -> 5 -------链表b:1 -> 1 -> 2 -> 3 今天不加思考的思路: ----想着为了节省内存空间,将合并的内容全都放到链表a中。先定义一头结点,然后将头结点指向首元...
  • ** 将两无序链表合并为一个有序链表,从小到大合并,不另外占领空间, **
  • 合并k个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。 示例: 输入: [ 1->4->5, 1->3->4, 2->6 ] 输出: 1->1->2->3->4->4->5->6 来源:力扣(LeetCode) 链接...
  • 题目:合并k个有序链表 题目描述: 合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。 示例: 输入: [ 1-&gt;4-&gt;5, 1-&gt;3-&gt;4, 2-&gt;6 ] 输出: ...
  • 有如下两个有序链表str1和str22.合并后的新链表的头结点定义为newpHead,采用摘结点法:三、代码实现(c语言)sListNode*MergeList(sListNode*FirpHead,sListNode*SecpHead){if(FirpHead==NULL){returnSecpHead;}if(S....
  • 合并个有序链表 自信满满地以为这是道水题,写完代码测试样例也通过了,可是还是WA了。 向超级奈斯的助教老哥求救之后终于明白了,能出问题的地方太多了,我这是写了什么破程序。 具体原因应该是我想的方法不太...
  • 将两升序链表合并成一升序链表,新链表是给定两个链表的节点组成的 递归 struct ListNode { int val; struct ListNode *next; }; struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2)...
  • 在此题中,需要先讨论L1为空或L2为空或均为空的情况,否则会出现runtime error的报错,因为当一个链表为空的时候会出现越界情况 (产生runtime error的几原因: ①除以零; ②数组越界:int a[3]; a[10000000]=10;...
  • 1.题目要求这是一道求职面试时经常要求手写...如果第一次做该题,很容易会想到使用新链表来存储合并后的有序链表。虽然可以如此实现,但是不符合常规解法和面试官的要求。2.非递归实现算法过程:输入:两有序的单...
  • 个有序链表合并

    2019-03-14 11:16:17
    将两个有序链表合并成一个链表合并后的链表仍然是有序的,依次输出合并后的链表的元素值,并求出第奇数位置元素之和

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 7,009
精华内容 2,803
关键字:

c语言合并k个有序链表

c语言 订阅