您现在的位置是:首页 > 正文

c语言合并k个有序链表,经典算法——合并K个有序链表(示例代码)

2024-02-01 00:39:04阅读 2

一、题目要求:

将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

网站文章

  • JavaScript数组

    数组1. 定义数组(array)是按次序排列的⼀组值。每个值的位置都有编号(从0开始),整个数组⽤⽅括号表⽰。var arr = ['a', 'b', 'c'];上⾯代码中的 a 、 b 、 c 就构成⼀个数组,两端的⽅括号是数组的标志。 a 是0号位置, b 是1号位置, c 是2号位置。除了在定义时赋值,数组也可以先定义后赋值。var arr = []; arr[0] = ...

    2024-02-01 00:38:58
  • AVFoundation的介绍

    AVFoundation的介绍

    一、简述 AVFoundation是一个OC媒体数据的高级框架。AVFoundation的构建考虑到了目前的硬件环境和应用程序,其设计过程高度依赖多线程机制。充分利用了多核硬件的优势并大量使用block和GCD机制,将复杂的计算机进程放到了后台线程运行。会自动提供硬件加速操作,确保在大部分设备上应用程序能以最佳性能运行。该框架就是针对64位处理器设计的,可以发挥64位处理器的所有优势。 二

    2024-02-01 00:38:50
  • excel粘贴时出现故障_Word粘贴时出现“文件未找到:MathPage.WLL”的解决方案

    excel粘贴时出现故障_Word粘贴时出现“文件未找到:MathPage.WLL”的解决方案

    问题:每次装完MathType后,在word里面进行粘贴操作时,总是出现“运行时错误‘53’:文件未找到:MathPage.WLL”。面对这种情况每次都要花点时间找真正的解决方案,然而并不是所有人提供...

    2024-02-01 00:38:43
  • 输出1~n的全排列(递归法) 热门推荐

    #include #include #include #include using namespace std; int a[1000]={0};//保存数列的数组,默认每个位置都是0 int book[1000]={0};//记录一个数有没有在数组里 int n;//1~n void A(int pos)//向a[pos]填数 { if(pos==n+1)//递归边界

    2024-02-01 00:38:14
  • oracle commit提交到底作了什么

    oracle commit所作的工作如下:1,产生一个scn 与此事务相关联的undo tablespace的itl标志为提交即flag为-c--; 并且为此事务分配一个唯一的scn并记录到undo tablespace的事...

    2024-02-01 00:38:07
  • JAVA继承和多态详细讲解

    JAVA继承和多态详细讲解

    面向对象编程的重要知识:继承和多态。通过类的继承机制,可以使用已有的类为基础派生出新类,无需编写重复的程序代码,很好地实现程序代码复用。多态是面向对象编程中继封装和继承之后的另一大特征,它具体是指同一...

    2024-02-01 00:37:38
  • Java二进制小数表示_《Java编程的逻辑》笔记9--小数的二进制表示

    Java二进制小数表示_《Java编程的逻辑》笔记9--小数的二进制表示

    小数计算为什么会出错?简要答案实际上,不是运算本身会出错,而是计算机根本就不能精确的表示很多数,比如0.1这个数。计算机是用一种二进制格式存储小数的,这个二进制格式不能精确表示0.1,它只能表示一个非...

    2024-02-01 00:37:29
  • C#使用OpenCVSharp进行轮廓检测

    在计算机视觉领域中,轮廓检测是一项常见的任务,它可以帮助我们找到图像中的物体边缘或形状边界。在本文中,我们将介绍如何使用C#和OpenCVSharp库实现轮廓检测。在上述代码中,我们首先读取了输入图像...

    2024-02-01 00:37:23
  • 通过PXE服务器批量安装系统

    通过PXE批量部署服务器

    2024-02-01 00:36:56
  • c语言基础局部变量与全局变量

    局部变量1. 在函数内部定义的变量2. 生命周期:从变量定义到函数结束3. 作用域:从变量定义到函数结束全局变量1. 在函数外部定义的变量2. 生命周期:从程序创建到程序销毁(全局变量的地址一旦文件编...

    2024-02-01 00:36:49