Merge Two Sorted Lists

두 개의 LinkedList를 정렬하여 합치는 문제이다. leetcode에서 제공하는 커스텀 클래스이며, 생성자를 잘 이용해 주어야 한다.

 

두 개의 리스트를 차례대로 확인하는 방법도 있겠지만 편의성을 위해 PriorityQueue를 이용하여 문제를 해결해보았다. 두 리스트의 값을 전부 넣은 이후 순서대로 꺼내서 새로 이어 주었다.

/**  
 * 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; } * } */  
import java.util.*;  
  
class Solution {  
  
    PriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> b.compareTo(a));  
  
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {  
        ListNode answer = null;  
        pqAddAllList(list1);  
        pqAddAllList(list2);  
        while(!pq.isEmpty()){  
            answer = new ListNode(pq.poll(), answer);  
        }  
  
        return answer;  
    }  
  
    private void pqAddAllList(ListNode list){  
        while(list != null){  
            pq.add(list.val);  
            list = list.next;  
        }  
    }  
}