Merge K Sorted List

📌 문제

• 여러 개의 ListNode가 들어있는 ListNode 배열이 주어진다. 해당 ListNode들을 오름차순으로 정렬해서, 새로운 노드를 만들어서 반환하라.

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

📌 문제 풀이

• brute force로 풀어볼까 했으나, 딱 봐도 시간복잡도도 그렇고, 풀이도 좋지 못할 것 같다. 그리고 null 값이 들어올 수 있기 때문에, null check를 하는 것도 복잡하다.
• Heapq ( ProrityQueue ) 와 ListNode를 이용하면 쉽게 풀 수 있다.

• ListNode[] lists 의 값을 PriorityQueue 에 넣는다. 이 때의 Comparator ( 정렬기준 ) 은 Integer.compare( n1.val , n2.val ) 을 해주면 오름차순이 된다.
• pq가 null이 될 때까지 loop를 돌고, 값을 뺄 때 해당 노드의 다음 값이 null이 아니라면 다시 큐에 넣어준다.

📌 코드

public class Main {
    public static void main(String[] args) {
        ListNode li1 = new ListNode(1);
        li1.add(4);
        li1.add(5);

        ListNode li2 = new ListNode(1);
        li2.add(3);
        li2.add(4);

        ListNode li3 = new ListNode(2);
        li3.add(7);

        ListNode[] list = new ListNode[3];

        list[0] = li1;
        list[1] = li2;
        list[2] = li3;

        Solution solution = new Solution();
        ListNode listNode = solution.mergeKLists(list);

        listNode.print();
    }
      public static class ListNode {
          Integer val;
          ListNode next;
          ListNode() {}
          ListNode(int val) { this.val = val; }
          ListNode(int val, ListNode next) { this.val = val; this.next = next; }

          // this 를 받을 방법을 못하고, next 로 조작하고 있었다.
          void add(int val){
              ListNode node = new ListNode(val);
              ListNode n = this;

              while(n.next !=null){
                  n=n.next;
              }
              n.next = node;
          }

          void print(){
              ListNode node = this;

              while(node.next!=null){
                  System.out.println(node.val);
                  node=node.next;
              }
              System.out.println(node.val);
          }
      }

    static class Solution {

        static Comparator<ListNode> comp = new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return Integer.compare(o1.val,o2.val);
            }
        };

        public ListNode mergeKLists(ListNode[] lists) {
            PriorityQueue<ListNode> pq = new PriorityQueue<>(comp);

            for(ListNode node : lists){
                if(node == null) continue;
                pq.offer(node);
            }

            ListNode res = new ListNode(0);
            ListNode temp = res;

            while(!pq.isEmpty()){
                ListNode poll = pq.poll();
                if(poll.next != null) pq.offer(poll.next);
                temp.next = poll;
                temp = temp.next;
            }
            return res.next;
        }
    }
}