合并 K 个升序链表

LeetCode23题目

给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 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;
  1

• ListNode *next;
  1

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

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

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

• };
  /
  class Solution {
  public:
  ListNode mergeKLists(vector& lists) {
  std::multimap mValueIndex;
  for (int i = 0; i < lists.size();i++ )
  {
  auto& p = lists[i];
  if (nullptr == p)
  {
  continue;
  }
  mValueIndex.emplace(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()->second;
   	mValueIndex.erase(mValueIndex.begin());
   	if (nullptr == lists[index])
   	{
   		continue;
   	}
   	mValueIndex.emplace(lists[index]->val,index);
   	lists[index] = lists[index]->next;
   }
  
   return pRet;
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24

  }
  };

2023年8月6号一

class Solution {
public:
ListNode* mergeKLists(vector& lists) {
if (lists.empty())
{
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& lists) {
if (lists.empty())
{
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;
}
};

其它

视频课程

如果你觉得复杂，想从简单的算法开始，可以学习我的视频课程。
https://edu.csdn.net/course/detail/38771
我的其它课程
https://edu.csdn.net/lecturer/6176

测试环境

win7 VS2019 C++17

相关下载

doc版文档，排版好
https://download.csdn.net/download/he_zhidan/88348653