LeetCode 문제 풀이 노트 - 23. K 개의 정렬 링크 를 합 칩 니 다 (분 치 법)

제목: k 개의 정렬 링크 를 합 쳐 합 친 정렬 링크 를 되 돌려 줍 니 다.알고리즘 의 복잡 도 를 분석 하고 설명 하 십시오.
예시:
입력: [1 - > 4 - > 5, 1 - > 3 - > 4, 2 - > 6] 출력: 1 - > 1 - > 2 - > 3 - > 4 - > 4 - > 5 - > 6
문제 풀이: 이 문 제 를 참고 하 세 요. 21. 두 개의 질서 있 는 링크 를 합 칩 니 다.①: k 개의 정렬 링크 를 두 번 정렬 하고 k - 1 번 배열 한 후에 최종 결 과 는 합병 한 결과 이다. 시간 복잡 도: O (kN), 그 중에서 k 는 링크 의 수량 으로 모두 N 개의 노드 가 마지막 링크 에 있다.공간 복잡 도: O (1).코드 는 다음 과 같 습 니 다:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        int n=lists.length;
        if(n==0||lists==null) return null;
        for(int i=0;i<n-1;i++){
            lists[i+1]=mergeTwoLists(lists[i],lists[i+1]);
        }
        return lists[n-1];
    }
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1==null) return l2;
        if(l2==null) return l1;
        ListNode l1_temp=new ListNode(0);
        ListNode l2_temp=new ListNode(0);
        ListNode result=new ListNode(0);
        l1_temp=l1;
        l2_temp=l2;
        while(true){
            if(l1_temp.val>=l2_temp.val){
                result.next=l2_temp;
                l2_temp=l2_temp.next;
            }
            else {
                result.next=l1_temp;
                l1_temp=l1_temp.next;
            }
            result=result.next;
            if(l1_temp==null) {
                result.next=l2_temp;
                break;
            }
            if(l2_temp==null){
                result.next=l1_temp;
                break;
            }
        }
            if(l1.val>=l2.val) return l2;
            else return l1;
    }
}

②: 생각해 보 니 최적화 할 수 있 는 부분 이 있 고 k 개 배열 의 합병 에 대해 분 치 법 을 사용 하여 합병 시간 이 너무 오래 걸 리 는 것 을 방지 할 수 있다.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        int n=lists.length;
        if(n==0||lists==null) return null;
        while(n>1){
            if(n%2==1) lists[n-2]=mergeTwoLists(lists[n-2],lists[n-1]);
            for(int i=0;i<n/2;i++){
                lists[i]=mergeTwoLists(lists[2*i],lists[2*i+1]);
            }
            n/=2;
        }
        return lists[0];
    }
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1==null) return l2;
        if(l2==null) return l1;
        ListNode l1_temp=new ListNode(0);
        ListNode l2_temp=new ListNode(0);
        ListNode result=new ListNode(0);
        l1_temp=l1;
        l2_temp=l2;
        while(true){
            if(l1_temp.val>=l2_temp.val){
                result.next=l2_temp;
                l2_temp=l2_temp.next;
            }
            else {
                result.next=l1_temp;
                l1_temp=l1_temp.next;
            }
            result=result.next;
            if(l1_temp==null) {
                result.next=l2_temp;
                break;
            }
            if(l2_temp==null){
                result.next=l1_temp;
                break;
            }
        }
            if(l1.val>=l2.val) return l2;
            else return l1;
    }
}

③: 참고 할 수 있 는 재 귀 분 치 법 도 있 지만 재 귀 는 시간 이 초과 되 기 때문에 코드 만 공유 하고 정 수 를 취하 면 된다.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length==0||lists==null) return null;
        return recursion(lists,0,lists.length-1);
    }
    public ListNode recursion(ListNode[] lists,int left,int right){
        if(right==left) return lists[right];
        int mid=(right+left)/2;
        ListNode list1=new ListNode();
        ListNode list2=new ListNode();
        list1=recursion(lists,0,mid);
        list2=recursion(lists,mid+1,right);
        return mergeTwoLists(list1,list2);
    }
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1==null) return l2;
        if(l2==null) return l1;
        ListNode l1_temp=new ListNode(0);
        ListNode l2_temp=new ListNode(0);
        ListNode result=new ListNode(0);
        l1_temp=l1;
        l2_temp=l2;
        while(true){
            if(l1_temp.val>=l2_temp.val){
                result.next=l2_temp;
                l2_temp=l2_temp.next;
            }
            else {
                result.next=l1_temp;
                l1_temp=l1_temp.next;
            }
            result=result.next;
            if(l1_temp==null) {
                result.next=l2_temp;
                break;
            }
            if(l2_temp==null){
                result.next=l1_temp;
                break;
            }
        }
            if(l1.val>=l2.val) return l2;
            else return l1;
    }
}

대신 해제