Skip to content

LeetCode: 23-Merge k Sorted Lists 解題紀錄

Last Updated on 2021-07-20 by Clay

題目

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Example 2:

Input: lists = []
Output: []

Example 3:

Input: lists = [[]]
Output: []
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Constraints:

  • k == lists.length
  • 0 <= k <= 10^4
  • 0 <= lists[i].length <= 500
  • -10^4 <= lists[i][j] <= 10^4
  • lists[i] is sorted in ascending order.
  • The sum of lists[i].length won’t exceed 10^4.

解題思路

這個題目我嘗試的解題方法比較暴力，或許沒什麼參考性也說不一定。

(處理愛貓生病，暫時停止撰寫內文，純做紀錄)

/**
 * 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<int> v;
        
        // Read all list
        for (int i=0; i<lists.size(); i++) {
            ListNode* readNode = new ListNode(0, lists[i]);
            
            while (readNode->next != NULL) {
                v.push_back(readNode->next->val);
                readNode->next = readNode->next->next;
            }
        }
        
        // Sort
        sort(v.begin(), v.end());
        
        // Create
        ListNode* head = new ListNode();
        head->val = -1;
        ListNode* currentNode = new ListNode(0, head);
        
        for (int i=0; i<v.size(); i++) {
            ListNode* newNode = new ListNode();
            currentNode->next->val = v[i];
            
            if (i != v.size()-1) {
                ListNode* head = new ListNode();
                currentNode->next->next = newNode;
                currentNode->next = currentNode->next->next;
            }
            else {
                currentNode->next->next = NULL;
            }
        }
        
        cout << head->val << endl;
        
        // Excepted
        if (head->val == -1 and head->next == NULL) {
            return NULL;
        }
        
        return head;
    }
};


References

Tags:

Leave a Reply