LeetCode (23) - Merge k Sorted Lists

하단 Title 클릭 시 해당 문제 페이지로 이동합니다.

- Merge k Sorted Lists

• Acceptance: 46.4%
• Difficulty: Hard

문제 설명

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 will not exceed 10^4.

예시 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

예시 2

Input: lists = []
Output: []

예시 3

Input: lists = [[]]
Output: []

문제 풀이

• 그냥 하라는대로 하니까 풀리는 문제.

1. 각 list를 비교해서 가장 작은 값을 가진 list index를 저장.
2. 해당 list의 head를 result에 붙여주고 list = list.next 로 한 칸 이동

• 여러 풀이법이 존재하는데, Priority Queue를 사용하는 방법과, Divide and Conquer로 list를 두 개씩 쪼개어 정렬 후 합치는 방법을 사용하면 훨씬 속도가 빠를것 같다.

코드

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        int listLength = lists.length, valid;
        ListNode result = new ListNode(), cur = result;

        while (true) {
            valid = 0;
            int index = 0, value = Integer.MAX_VALUE;

            for (int i = 0; i < listLength; i++) {
                if (lists[i] != null) {
                    valid++;

                    if (lists[i].val <= value) {
                        index = i;
                        value = lists[i].val;
                    }
                }
            }

            if (valid > 0) {
                cur.next = lists[index];
                cur = cur.next;
                lists[index] = lists[index].next;
            } else {
                break;
            }
        }

        return result.next;
    }
}