C++算法：合并 K 个升序链表

C++算法：合并 K 个升序链表

题目

给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
示例 2：
输入：lists = []
输出：[]
示例 3：
输入：lists = [[]]
输出：[]

2023年5月6号

/**

• Definition for singly-linked list.

• struct ListNode {

• int val;
  

• ListNode *next;
  

• ListNode() : val(0), next(nullptr) {}
  

• ListNode(int x) : val(x), next(nullptr) {}
  

• ListNode(int x, ListNode *next) : val(x), next(next) {}
  

• };
  /
  class Solution {
  public:
  ListNode mergeKLists(vector<ListNode*>& lists) {
  std::multimap<int, int> mValueIndex;
  for (int i = 0; i < lists.size();i++ )
  {
  auto& p = lists[i];
  if (nullptr == p)
  {
  continue;
  }
  place(p->val, i);
  p = p->next;
  }

   ListNode* pRet = nullptr, *pNode = nullptr;while (mValueIndex.size()){if (nullptr == pNode){pRet = pNode = new ListNode(mValueIndex.begin()->first);}else{pNode->next = new ListNode(mValueIndex.begin()->first);pNode = pNode->next;}int index = mValueIndex.begin()->ase(mValueIndex.begin());if (nullptr == lists[index]){continue;}place(lists[index]->val,index);lists[index] = lists[index]->next;}return pRet;
  

  }
  };

2023年8月6号一

class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if (pty())
{
return nullptr;
}
while (lists.size() > 1)
{
const int size = lists.size();
for (int i = 0; i < size / 2; i++)
{
lists[i] = Merge(lists[i], lists[size - 1 - i]);
lists.pop_back();
}
}
return lists[0];
}
ListNode* Merge(ListNode* p1, ListNode* p2)
{
ListNode* pHead = nullptr, *pTail = nullptr;
while (p1 && p2)
{
if (p1->val < p2->val)
{
if (nullptr == pHead)
{
pHead = p1;
}
else
{
pTail->next = p1;
}
pTail = p1;
p1 = p1->next;
pTail->next = nullptr;
}
else
{
if (nullptr == pHead)
{
pHead = p2;
}
else
{
pTail->next = p2;
}
pTail = p2;
p2 = p2->next;
pTail->next = nullptr;
}
}
if (nullptr != p1)
{
if (nullptr == pTail)
{
pHead = pTail = p1;
}
else
{
pTail->next = p1;
}
}
else if (nullptr != p2)
{
if (nullptr == pTail)
{
pHead = pTail = p2;
}
else
{
pTail->next = p2;
}
}
return pHead;
}
};

2023年8月6号二

class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if (pty())
{
return nullptr;
}
const int size = lists.size();
for (int i = 1; i < size; i++)
{
lists[0] = Merge(lists[i], lists[0]);
}
return lists[0];
}
ListNode* Merge(ListNode* p1, ListNode* p2)
{
ListNode* pHead = nullptr, *pTail = nullptr;
while (p1 && p2)
{
if (p1->val < p2->val)
{
if (nullptr == pHead)
{
pHead = p1;
}
else
{
pTail->next = p1;
}
pTail = p1;
p1 = p1->next;
pTail->next = nullptr;
}
else
{
if (nullptr == pHead)
{
pHead = p2;
}
else
{
pTail->next = p2;
}
pTail = p2;
p2 = p2->next;
pTail->next = nullptr;
}
}
if (nullptr != p1)
{
if (nullptr == pTail)
{
pHead = pTail = p1;
}
else
{
pTail->next = p1;
}
}
else if (nullptr != p2)
{
if (nullptr == pTail)
{
pHead = pTail = p2;
}
else
{
pTail->next = p2;
}
}
return pHead;
}
};

其它

视频课程

如果你觉得复杂，想从简单的算法开始，可以学习我的视频课程。

我的其它课程

测试环境

win7 VS2019 C++17

相关下载

doc版文档，排版好