leetcode Merge k Sorted Lists(Java)

题目链接：点击打开链接

类型：合并

解法：分治

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode mergeKLists(ListNode[] lists) { int len = lists.length; return partition(lists, 0, len-1); } private ListNode partition(ListNode[] lists, int s, int e) { if (s == e) return lists[s]; if (s < e) { int m = (s+e)/2; ListNode r1 = partition(lists, s, m); ListNode r2 = partition(lists, m+1, e); return merge(r1, r2); } else { return null; } } private ListNode merge(ListNode l1, ListNode l2) { if (l1 == null) return l2; if (l2 == null) return l1; if (l1.val < l2.val) { l1.next = merge(l1.next, l2); return l1; } else { l2.next = merge(l1, l2.next); return l2; } } }