[LeetCode] 23. Merge k Sorted Lists - Java

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

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 <= 104
• 0 <= lists[i].length <= 500
• -104 <= lists[i][j] <= 104
• lists[i] is sorted in ascending order.
• The sum of lists[i].length will not exceed 104.

---

풀이

풀이 과정

linked list들로 이루어진 배열 lists가 주어질 때 모든 주어진 리스트를 오름차순으로 병합된 리스트를 구해야한다.

우선순위 큐를 이용하여 풀이한다.
일반적인 큐는 먼저 들어온 데이터가 먼저 나가게 되는 FIFO(First In First Out) 형태의 자료구조이지만 우선순위 큐는 우선순위가 높은 데이터가 먼저 나가게 되는 자료구조이다.

우선 lists 배열이 빈 값인 경우 바로 null을 반환한다.

// 전달받은 리스트가 null인 경우 바로 null return
if(lists == null) return null;

 

탐색에 사용할 우선순위 큐를 선언한다. 이 때 리스트의 값을 기준으로 우선순위가 정의 되어야 하기 때문에 다음과 같이 리스트의 값을 기준으로 비교하도록 생성한다.

// 탐색에 사용할 우선순위 큐 선언
// 리스트 노드의 값을 기준으로 정렬
PriorityQueue<ListNode> pq = new PriorityQueue<>((a1,a2)->{
    return a1.val-a2.val;
});

 

리스트들을 합치는 과정은 다음과 같다.

1. 모든 리스트 노드를 우선순위 큐에 삽입
2. 우선순위가 가장 높은 리스트 노드(노드의 값이 가장 작은 리스트 노드)를 하나 꺼냄
3. 꺼낸 리스트 노드를 정답에 추가
4. 꺼낸 리스트 노드의 next 값이 존재한다면 우선순위 큐에 next 값 삽입
5. 큐가 빌 때 까지 1 ~ 4의 과정을 반복

 

반복문을 이용하여 lists 배열에 있는 리스트들을 큐에 삽입한다.

// lists 배열에 있는 리스트들을 큐에 삽입
for(int i = 0; i < lists.length; i++){
    if(lists[i] != null) pq.offer(lists[i]);
}

 

탐색에 필요한 변수값들을 선언한다.

// 반환할 정답 리스트를 생성
ListNode answer = new ListNode(0);
// 노드를 추가하기 위한 포인터
ListNode pointer = answer;
// 현재 탐색중인 노드
ListNode curNode = null;

 

큐에서 값을 꺼내어 정답 리스트에 추가하고 꺼낸 값의 next 값을 큐에 삽입하는 과정을 큐가 빌 때 까지 반복한다.

// 큐가 빌 때 까지 반복
while(!pq.isEmpty()){
    // 큐에서 값을 꺼냄
    curNode = pq.poll();
    // 정답 리스트에 추가
    pointer.next = curNode;
    // 포인터 이동
    pointer = pointer.next;
    // 현재 탐색중인 노드의 next 값이 존재하는 경우 next 값을 큐에 다시 삽입
    if(curNode.next != null) pq.offer(curNode.next);
}

 

최종적으로 만들어진 리스트 노드를 return

// 정답 리스트 return
// 임의의 값을 넣어 생성하였으므로 next부터 return
return answer.next;

---

최종 코드

/**
 * 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) {
        // 전달받은 리스트가 null인 경우 바로 null return
        if(lists == null) return null;

        // 탐색에 사용할 우선순위 큐 선언
        // 리스트 노드의 값을 기준으로 정렬
        PriorityQueue<ListNode> pq = new PriorityQueue<>((a1,a2)->{
            return a1.val-a2.val;
        });

        // lists 배열에 있는 리스트들을 큐에 삽입
        for(int i = 0; i < lists.length; i++){
            if(lists[i] != null) pq.offer(lists[i]);
        }

        // 반환할 정답 리스트를 생성
        ListNode answer = new ListNode(0);
        // 노드를 추가하기 위한 포인터
        ListNode pointer = answer;
        // 현재 탐색중인 노드
        ListNode curNode = null;

        // 큐가 빌 때 까지 반복
        while(!pq.isEmpty()){
            // 큐에서 값을 꺼냄
            curNode = pq.poll();
            // 정답 리스트에 추가
            pointer.next = curNode;
            // 포인터 이동
            pointer = pointer.next;
            // 현재 탐색중인 노드의 next 값이 존재하는 경우 next 값을 큐에 다시 삽입
            if(curNode.next != null) pq.offer(curNode.next);
        }

        // 정답 리스트 return
        // 임의의 값을 넣어 생성하였으므로 next부터 return
        return answer.next;
    }
}

---