题意:合并几个有序链表,使结果也是有序的
题解1:循环遍历这几个链表头,将最小的加入结果链表中
1 class Solution { 2 public: 3 ListNode* mergeKLists(vector<ListNode*>& lists) { 4 ListNode* res = NULL; 5 ListNode* cur = res; 6 while (true) 7 { 8 int target = 0; 9 while (target < lists.size() && lists[target] == NULL) 10 target++; 11 if (target >= lists.size()) 12 break; 13 for (auto i = 0; i < lists.size(); i++) { 14 if (lists[i] == NULL) { 15 continue; 16 } 17 18 if (lists[target]->val > lists[i]->val) 19 target = i; 20 } 21 22 if (res == NULL) { 23 res = new ListNode(lists[target]->val); 24 cur = res; 25 } 26 else { 27 cur->next = new ListNode(lists[target]->val); 28 cur = cur->next; 29 } 30 lists[target] = lists[target]->next; 31 } 32 return res; 33 } 34 };
题解2:有一个取巧的办法,就是把所有元素取出来加入数组,对这个数组排序,再放回链表中
1 class Solution { 2 public: 3 ListNode* mergeKLists(vector<ListNode*>& lists) { 4 vector<int> a; 5 for (auto i = 0; i < lists.size(); i++) 6 { 7 ListNode* p = lists[i]; 8 while (p != NULL) 9 { 10 a.push_back(p->val); 11 p = p->next; 12 } 13 } 14 sort(a.begin(), a.end()); 15 ListNode* res = new ListNode(a[0]); 16 ListNode* cur = res; 17 for (auto i = 1; i < a.size(); i++) { 18 cur->next = new ListNode(a[i]); 19 cur = cur->next; 20 } 21 return res; 22 } 23 };