LeetCode 23. Merge k Sorted Lists

LeetCode 23. Merge k Sorted Lists

DescriptionExampleCodeConclusion

Description

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

Example

Input: [ 1->4->5, 1->3->4, 2->6 ] Output: 1->1->2->3->4->4->5->6

Code

java /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode merge2Lists(ListNode list1, ListNode list2) { ListNode newList = new ListNode(0); ListNode pNode = newList; while(list1 != null || list2 != null) { if(list2 == null || (list1 != null && list1.val < list2.val)) { pNode.next = list1; list1 = list1.next; } else { pNode.next = list2; list2 = list2.next; } pNode = pNode.next; } return newList.next; } public ListNode mergeKListsCore(ListNode[] lists, int left, int right) { int len = right - left + 1; if(len == 1) { return lists[left]; } else if(len == 2) { return merge2Lists(lists[left], lists[right]); } int mid = (left + right) / 2; ListNode lList = mergeKListsCore(lists, left, mid); ListNode rList = mergeKListsCore(lists, mid+1, right); return merge2Lists(lList, rList); } public ListNode mergeKLists(ListNode[] lists) { int len = lists.length; if(len == 0) return null; return mergeKListsCore(lists, 0, len-1); } } Others’ SolutionPriorityQueuejava public class Solution { public ListNode mergeKLists(List<ListNode> lists) { if (lists==null||lists.size()==0) return null; PriorityQueue<ListNode> queue= new PriorityQueue<ListNode>(lists.size(),new Comparator<ListNode>(){ @Override public int compare(ListNode o1,ListNode o2){ if (o1.val<o2.val) return -1; else if (o1.val==o2.val) return 0; else return 1; } }); ListNode dummy = new ListNode(0); ListNode tail=dummy; for (ListNode node:lists) if (node!=null) queue.add(node); while (!queue.isEmpty()){ tail.next=queue.poll(); tail=tail.next; if (tail.next!=null) queue.add(tail.next); } return dummy.next; } }

Conclusion

多路递归归并评论区里的优先队列也挺好的