302.LeetCode | 23. 合并K个升序链表

vlambda
2021-05-08

302.LeetCode | 23. 合并K个升序链表

每天一个开发小知识

题目

给你一个链表数组，每个链表都已经按升序排列

请你将所有链表合并到一个升序链表中，返回合并后的链表

思路

这题是双指针的升级版

——多，多，多指针

由于链表数组的大小不确定

所以我们用一个对应的数组存放每个链表的游标指针

每次寻找当前最小值时

遍历这个游标指针的数组

解法：多指针

时间复杂度 O(n*m)，空间复杂度 O(n)

其中 n 为输入数组的大小，m 为每个链表的平均长度

对于每个节点，需要比较 n - 1 次才能确定该节点的位置

所以时间复杂度为 O(n*m)

/** * 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) { vector<ListNode*> pos; for (auto iter : lists) { pos.push_back(iter); }
 ListNode * dummy = new ListNode(); ListNode * p = dummy;
 while (NULL != p) { int index = -1; for (int i = 0; i < pos.size(); ++i) { if (NULL != pos[i]) { if (-1 == index || pos[i]->val < pos[index]->val) { index = i; } } }
 if (-1 != index) { p->next = pos[index]; pos[index] = pos[index]->next; }
 p = p->next; }
 return dummy->next; }};