Merge k Sorted Lists

🔗 문제 링크

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

🔍 문제 설명

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.

⚠️ 제한사항

• $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.$

🗝 풀이 (언어 : Java)

단순하게 따로 정의한 LinkedList 원소들을 모두 추출해서 List에 넣어주고, List를 정렬해준 후에 다시 LinkedList에 넣어주었다. 다른 풀이 방법으로 최소힙을 이용한 PriorityQueue를 이용해서 정렬하는 방법도 가능하다.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        List<Integer> answer = new ArrayList<>();
        for (ListNode l : lists) {
            ListNode cur = l;
            while (cur != null) {
                answer.add(cur.val);
                cur = cur.next;
            }
        }
        Collections.sort(answer);
        ListNode head = new ListNode(), tmp = head;
        for (int i : answer) {
            tmp.next = new ListNode(i);
            tmp = tmp.next;
        }
        return head.next;
    }
}