[LeetCode] 23. Merge k Sorted Lists

轉自LeetCode

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

<Solution>

這題是 Merge Two Sorted List 的延伸

現在有 k 個 list，最直接想法就是先 merge 兩個，然後再和之後每一個 merge

meage list_1 和 list_2，拿到 list_a
meage list_a 和 list_3，拿到 list_b
meage list_b 和 list_4，拿到 list_c

list_c 就是答案

但這樣不夠有效率

這題是要 merge 好 k 個 sorted list，其實就是在做 merge sort 一樣

要用 divide and conquer 的方式來處理

有 list_1，list_2，list_3，list_4

list_1 和 list_2 merge 得到 list_a，list_3 和 list_4 merge 得到 list_b

最後再 merge list_a 和 list_b 就可以得到答案

code 如下

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:
	ListNode* mergeKLists(vector<ListNode*>& lists) {
	if(lists.size() == 0) {
	return NULL;
	}
	return divideAndConquer(0, lists.size()-1, lists);
	}
	//> merge two sorted list
	ListNode *mergeList(ListNode *list_1, ListNode *list_2) {
	ListNode *tmpHead = new ListNode(0);
	ListNode *tmpCurr = tmpHead;
	while(list_1 && list_2) {
	if(list_1->val < list_2->val) {
	tmpCurr->next = list_1;
	tmpCurr = list_1;
	list_1 = list_1->next;
	}
	else {
	tmpCurr->next = list_2;
	tmpCurr = list_2;
	list_2 = list_2->next;
	}
	}
	if(list_1) {
	tmpCurr->next = list_1;
	}
	if(list_2) {
	tmpCurr->next = list_2;
	}
	return tmpHead->next;
	}
	//> divide lists into left part and right part
	ListNode *divideAndConquer(const int &left, const int &right, vector<ListNode*>& lists) {
	if(left == right) {
	return lists[left];
	}
	else if(left == (right - 1)) {
	return mergeList(lists[left], lists[right]);
	}
	int mid = (left + right) / 2;
	ListNode *myList_1 = divideAndConquer(left, mid, lists);
	ListNode *myList_2 = divideAndConquer(mid+1, right, lists);
	return mergeList(myList_1, myList_2);
	}
	};

view raw mergeKthSortedLists_1.cpp hosted with ❤ by GitHub

解法 2 是運用到 min heap 的概念

可以使用 std::priority_queue，預設是 max heap

但只要改變用來比較的函數，就可以變成 min heap

使用 min heap 的想法如下

• 先把每個 list 的最小元素丟到 min heap

• 只要 min heap 不為空，持續以下動作

1. 拿出第一個元素，串到答案的 link list。因為 min heap 的特性，每次拿到的一定是當前最小的元素


2. 檢查當前的元素是否是最後一個元素，不是的話，再丟進去 min heap

code 如下

c++

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:
	//> make priority_queue become min heap
	struct myCmp {
	bool operator() (ListNode *a, ListNode *b) {
	return a->val > b->val;
	}
	};
	ListNode* mergeKLists(vector<ListNode*>& lists) {
	priority_queue<ListNode*, vector<ListNode*>, myCmp> minHeap;
	//> put smallest element of each list into minHeap
	for(int i = 0; i < lists.size(); i++) {
	if(lists[i]) {
	minHeap.push(lists[i]);
	}
	}
	ListNode *head = new ListNode(0);
	ListNode *curr = head;
	//> merge remaining elements
	while(!minHeap.empty()) {
	ListNode *tmp = minHeap.top();
	minHeap.pop();
	curr->next = tmp;
	curr = curr->next;
	if(tmp->next) {
	minHeap.push(tmp->next);
	}
	}
	return head->next;
	}
	};

view raw mergeKthSortedLists_2.cpp hosted with ❤ by GitHub

Kotlin

	/**
	* Example:
	* var li = ListNode(5)
	* var v = li.`val`
	* Definition for singly-linked list.
	* class ListNode(var `val`: Int) {
	* var next: ListNode? = null
	* }
	*/
	class Solution {
	fun mergeKLists(lists: Array<ListNode?>): ListNode? {
	val pq = PriorityQueue { v1: Int, v2: Int -> v1 - v2 }
	var pointer: ListNode?
	for (list in lists) {
	pointer = list
	while(pointer != null) {
	pq.add(pointer!!.`val`)
	pointer = pointer.next
	}
	}
	val dummyHead = ListNode(-1)
	var curr = dummyHead
	while(pq.isNotEmpty()) {
	curr.next = ListNode(pq.first())
	curr = curr.next
	pq.remove()
	}
	return dummyHead.next
	}
	}

view raw merge_k_sorted_lists.kt hosted with ❤ by GitHub