LeetCode（23）：合并K個排序連結清單 Merge k Sorted Lists（Java）

2019.6.7 #程式員筆試必備# LeetCode 從零單刷個人筆記整理（持續更新）

合并兩個有序連結清單可以很容易地想到歸并排序的方法。合并K個有序連結清單需要分治+歸并，對K個連結清單進行分治，對分治後的連結清單兩兩歸并排序即可。

傳送門：合并K個排序連結清單

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

合并 k 個排序連結清單，傳回合并後的排序連結清單。請分析和描述算法的複雜度。

示例:
輸入:
[
  1->4->5,
  1->3->4,
  2->6
]
輸出: 1->1->2->3->4->4->5->6
           

/**
 * 
 * @author ChopinXBP
 * Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
 * 合并 k 個排序連結清單，傳回合并後的排序連結清單。請分析和描述算法的複雜度。
 *
 */

public class MergekSortedLists {


	public class ListNode {
		int val;
		ListNode next;

		ListNode(int x) {
			val = x;
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

    public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null || lists.length == 0) return null;
        
        return mergeSolution(lists, 0, lists.length - 1);
    }
    
    public ListNode mergeSolution(ListNode[] lists, int begin, int end) {
    	if(begin == end) {
    		return lists[begin];
    	}else {
    		int mid = (begin + end) >> 1;
    		ListNode l1 = mergeSolution(lists, begin, mid);
    		ListNode l2 = mergeSolution(lists, mid + 1, end);
    		return mergeTwoLists(l1, l2);
    	}
    }
    
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    	if(l1 == null && l2 == null)return null;
    	if(l1 == null) return l2;
    	if(l2 == null) return l1;
    	
    	ListNode result = new ListNode(-1);
    	ListNode p = result;
    	ListNode pl1 = l1;
    	ListNode pl2 = l2;
    	while(pl1 != null && pl2 != null) {
    		if(pl1.val < pl2.val) {
    			p.next = pl1;
    			pl1 = pl1.next;
    		}else {
    			p.next = pl2;
    			pl2 = pl2.next;
    		}
    		p = p.next;
    	}
    	
    	if(pl1 == null) {
    		p.next = pl2;
    	}
    	if(pl2 == null) {
    		p.next = pl1;
    	}
    	
    	return result.next;
    }
}


           

#Coding一小時，Copying一秒鐘。留個言點個贊呗，謝謝你#