leetcode 23) Merge k Sorted Lists

LV. Hard 🥵

https://leetcode.com/problems/merge-k-sorted-lists/

Merge k Sorted Lists - LeetCode

 

문제

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: []

 

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.

 

문제 해결법

문제 난이도가 hard여서 겁먹었지만 정말 간단했던 문제!

 

lists에 담겨있는 모든 val값을 새로운 백터인 val_list에 저장해줬다.

val_list를 정렬 후 새롭게 ListNode 배열을 생성해서 리턴하면 끝!

 

해결 코드

class Solution {
private:
	vector<int> val_list;

public:
	ListNode* mergeKLists(vector<ListNode*>& lists) {
		setValList(lists);
		if (val_list.size() == 0)
			return new ListNode();
		sort(val_list.begin(), val_list.end());
		
		ListNode *start = new ListNode(val_list[0]);
		ListNode *before = start;
		for (int i = 1; i < val_list.size(); ++i) {
			ListNode *temp = new ListNode(val_list[i]);
			before->next = temp;
			before = temp;
		}
		return start;
	}
	
	// val list에 val값 전부 저장
	void setValList(vector<ListNode*>& lists) {
		ListNode *temp;

		for (int i = 0; i < lists.size(); ++i) {
			temp = lists[i];
			while (temp) {
				val_list.push_back(temp->val);
				temp = temp->next;
			}
		}
	}
};