[Java] LeetCode 23번 Merge k Sorted Lists

k개의 정렬된 링크드 리스트를 1개의 정렬된 링크드 리스트로 합치는 문제이다. 머지소트와 상당히 흡사하다. 그래서 list의 길이가 2라면 두 리스트를 합쳐주고, 3이상이라면 반씩 쪼개어서 다시 merge 과정을 진행해준다.

class Solution {
    public ListNode mergeTwo(ListNode first, ListNode second) {
        ListNode ret = new ListNode();
        ListNode cur = ret;
        while (first != null && second != null) {
            if (first.val < second.val) {
                cur.next = new ListNode(first.val);
                first = first.next;
            } else {
                cur.next = new ListNode(second.val);
                second = second.next;
            }
            cur = cur.next;
        }
        if (first != null) {
            cur.next = first;
        } else if (second != null) {
            cur.next = second;
        }
        return ret.next;
    }

    public ListNode mergeKLists(ListNode[] lists) {
        int n = lists.length;
        if (lists.length == 0) {
            return null;
        }
        if (lists.length == 1) {
            return lists[0];
        } else if (lists.length == 2) {
            return mergeTwo(lists[0], lists[1]);
        } else {
            ListNode[] left = new ListNode[n / 2];
            ListNode[] right = new ListNode[(n + 1) / 2];
            for (int i = 0; i < n / 2; i++) {
                left[i] = lists[i];
            }
            for (int i = 0; i < (n + 1) / 2; i++) {
                right[i] = lists[i + n / 2];
            }
            ListNode leftNode = mergeKLists(left);
            ListNode rightNode = mergeKLists(right);
            return mergeTwo(leftNode, rightNode);
        }
    }
}