leetcode 문제 풀이 - 23. Merge k 정렬 목록

제목: k 개의 질서 있 는 링크 를 합 쳐 설명 알고리즘 의 복잡 도 를 분석 합 니 다.
분석: 이 문 제 는 분포 식 시스템 에서 흔히 볼 수 있 습 니 다. 서로 다른 client 에서 온 sorted list 는 central server 에서 merge 해 야 합 니 다.해법 은 병합 정렬 과 유사 한 사고 이다. 바로 분 치 법 이다. 병합 정렬 을 모 르 는 친 구 는 병합 정렬 - 위 키 피 디 아 를 참조 하 십시오. 비교적 전형 적 인 O (nlogn) 의 정렬 알고리즘 인지 중요 하 다.
사고방식 은 먼저 두 개의 하위 임무 로 나 누 어 진 후에 하위 임 무 를 되 찾 고 마지막 에 되 돌아 오 는 것 이다.이 문제 도 마찬가지 입 니 다. 먼저 k 개의 list 를 반 으로 나 눈 다음 에 계속 구분 합 니 다. 나머지 두 개의 list 가 합 쳐 진 다 는 것 을 알 고 합병 할 때 두 개의 질서 있 는 링크 서브 과정 이 필요 합 니 다.익숙 하지 않 은 친 구 는 복습 해도 된다.코드 는 다음 과 같 습 니 다:

class Solution {
    public static ListNode mergeKLists(ListNode[] lists) {
        if(lists.length == 0) return null;
        return help(lists, 0, lists.length - 1);
    }
    public static ListNode help(ListNode[] lists, int l, int r) {
        int m = (l + r) / 2;
        if(l < r){
            return mergeTwoLists(help(lists, l, m), help(lists, m + 1, r));
        }
        return lists[l];

    }
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null || l2 == null) return l1==null? l2:l1;
        ListNode dummy = new ListNode(0);
        if(l1.val < l2.val){
            dummy.next = l1;
            l1 = l1.next;
        }else{
            dummy.next = l2;
            l2 = l2.next;
        }
        ListNode temp = dummy.next;
        while(l1 != null  && l2 != null){
            if(l1.val < l2.val){
                temp.next = l1;
                temp = temp.next;
                l1 = l1.next;
            }else{
                temp.next = l2;
                temp = temp.next;
                l2 = l2.next;
            }
        }
        temp.next = l1 == null ? l2:l1;
        return dummy.next;

    }

    public static void print(ListNode head){
        while(head != null){
            System.out.println(head.val);
            head = head.next;
        }

    }
    public static void main(String[] args) {
        ListNode l1 = new ListNode(4);
        ListNode l2 = new ListNode(5);
        ListNode l3 = new ListNode(6);
        ListNode l4 = new ListNode(1);
        ListNode l5 = new ListNode(2);
        ListNode l6 = new ListNode(3);

        l1.next = l2;
        l2.next = l3;
        l4.next = l5;
        l5.next = l6;

        ListNode[] lists = {l1,l4};

        print(mergeKLists(lists));
    }
}