Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
/** * 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) { if(lists == null || lists.length == 0) return null; if(lists.length < 2) return lists[0]; return merge(lists, 0, lists.length-1); } public ListNode merge(ListNode[] lists, int start, int end){ if(start >= end) return lists[start]; int mid = (start + end) / 2; ListNode left = merge(lists, start, mid); ListNode right = merge(lists, mid+1, end); return mergetwo(left, right); } public ListNode mergetwo(ListNode left, ListNode right){ if(left == null) return right; if(right == null) return left; ListNode dummy = new ListNode(0); ListNode node = dummy; while (left != null && right != null) { if(left.val < right.val) { node.next = left; node = node.next; left = left.next; } else { node.next = right; node = node.next; right = right.next; } } if(left != null) node.next = left; if(right != null) node.next = right; return dummy.next; }}新闻热点
疑难解答
