题目
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 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; } 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;
- }
};
2023年8月6号一
class Solution { public: ListNode* mergeKLists(vector<ListNode*>& 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<ListNode*>& 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
