生活随笔
收集整理的這篇文章主要介紹了
每天一道LeetCode-----合并两个/多个有序链表为一个新链表
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
Merge Sorted Array
原題鏈接Merge Sorted Array
意思是給定兩個有序數組，將其合并成一個有序數組，存在nums1中。
如果先只是簡單合并成一個新數組，然后將新數組賦值給nums1，基本就算完成了。現在考慮不適用其它內存空間，在nums1上原地合并新數組。
遇到的問題是如果nums1[i] > nums2[j]，那么nums1[i]的位置就應該被賦值給nums2[j]，可是nums1[i]原先的值應該放在哪里呢，接下來還有用這個nums1[i]和nums2[j+1]繼續比較呢。如果nums1[i]一直大于nums2[j]，那么所有的nums1[i]又應該放在哪里呢。
方法是在開始合并前就給nums1的前面留出n個大小的空間，而把nums1原來的數據全移動到后面的位置（這里是移動到nums1[n : m+n)），這樣，即使nums2全都小于nums1，nums2也可以原封不動的放進nums1中，并且不需要移動nums1原有的數據
0 1 2 3 4 5 下標
1 3 5 nums1
2 4 6 nums2初始時
0 1 2 3 4 5 下標
1 3 5 nums1
2 4 6 nums2開始合并
0 1 2 3 4 5 下標
1 1 3 5 nums1
1 2 1 3 5 nums1
1 2 3 1 3 5 nums1
1 2 3 4 3 5 nums1
1 2 3 4 5 5 nums1
1 2 3 4 5 6 nums1
合并完成
因為初始時nums1前面已經留有n個大小的空間（nums2的大小），所以在給nums1[0 : m+1)賦值時覆蓋的都是合并完成，被放到前面的數據，不會丟失數據
代碼如下
class Solution {
public:
void merge(
vector<int>& nums1,
int m,
vector<int>& nums2,
int n) {
for(
int i = m -
1; i >=
0; --i)nums1[i + n] = nums1[i];
int p1 = n;
int p2 =
0;
int idx =
0;
while(p1 < m + n && p2 < n){nums1[idx++] = (nums1[p1] > nums2[p2]) ? nums2[p2++] : nums1[p1++];}
while(p1 < m + n)nums1[idx++] = nums1[p1++];
while(p2 < n)nums1[idx++] = nums2[p2++];}
};
Merge Two Sorted Lists
原題鏈接Merge Two Sorted Lists
意思是合并兩個有序鏈表成為一個新的有序鏈表，比較簡單，依次比較即可
細節方法是構造一個頭節點，可以解決返回值是null的情況
class Solution {
public:ListNode
* mergeTwoLists(ListNode
* l1, ListNode
* l2) {ListNode
* header = new ListNode(
-1);ListNode
* cur
= header;
while(l1
|| l2){int n
= 0;
if(l1
== NULL || (l1
&& l2
&& l1
->val
> l2
->val)){n
= l2
->val;l2
= l2
->next;}
else if(l2
== NULL || (l1
&& l2
&& l1
->val
<= l2
->val)){n
= l1
->val;l1
= l1
->next;}cur
->next
= new ListNode(n);cur
= cur
->next;}ListNode
*ans
= header->next;delete
header;
return ans;}
};
Merge k Sorted Lists
原題鏈接Merge k Sorted Lists
意思是合并k個有序鏈表，要求合成的鏈表也是有序的
兩個鏈表時可以每次比較大小決定取哪個鏈表的值，k個就不能這么亂來了，不然復雜度會飆升。
可以維護一定大小的最小堆（優先級隊列），堆中元素是ListNode類型，每次取最小的，然后插入取出的節點的下一個節點（如果是null就不用插入），直到堆變空為止。
需要注意的是如果ListNode設計時內部重載了operator<函數，那么直接創建優先級隊列即可。但是題中給出的ListNode定義沒有提供這樣的函數，就需要自己實現，此時如果使用優先級隊列的話，模板參數要提供三個
class Solution {
public:ListNode* mergeKLists(
vector<ListNode*>& lists) {
if(lists.size() ==
0)
return NULL;
std::priority_queue<ListNode,
vector<ListNode>, cmp> pq;
for(
auto node : lists){
if(node != NULL)pq.push(
std::move(*node));}ListNode* header =
new ListNode(-
1);ListNode* cur = header;
while(pq.size() >
0){ListNode node = pq.top();pq.pop();cur->next =
new ListNode(node.val);cur = cur->next;
if(node.next)pq.push(
std::move(*node.next));}ListNode* ans = header->next;
delete header;
return ans;}
private:
struct cmp{
bool operator()(
const ListNode& lhs,
const ListNode& rhs){
return lhs.val > rhs.val;} };
};
總結
以上是生活随笔為你收集整理的每天一道LeetCode-----合并两个/多个有序链表为一个新链表的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
