首页 > 代码库 > Leetcode-Merge k Sorted Lists
Leetcode-Merge k Sorted Lists
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Have you met this question in a real interview?
Analysis:
record the current head of each list. Use binary insertation to arrange the head list, select the minimum one and add to the end of the return list.
Solution:
1 /** 2 * Definition for singly-linked list. 3 * public class ListNode { 4 * int val; 5 * ListNode next; 6 * ListNode(int x) { 7 * val = x; 8 * next = null; 9 * }10 * }11 */12 public class Solution {13 public ListNode mergeKLists(List<ListNode> lists) {14 //Consider the cases where the element in lists is NULL!15 for (int i=0;i<lists.size();i++)16 if (lists.get(i)==null){17 lists.remove(i);18 i--;19 }20 if (lists.size()==0) return null;21 if (lists.size()==1) return lists.get(0);22 23 ListNode preHead = new ListNode(0);24 ListNode end = preHead;25 List<ListNode> curList = new ArrayList<ListNode>();26 curList.add(lists.get(0));27 for (int i=1;i<lists.size();i++) binaryInsert(curList,lists.get(i));28 while (curList.size()!=0){29 if (curList.size()==1){30 end.next = curList.get(0);31 end = new ListNode(0);32 break;33 }34 ListNode target = curList.get(0); 35 curList.remove(0);36 if (target.next!=null) binaryInsert(curList,target.next);37 end.next = target;38 end = target;39 }40 end.next = null;41 return preHead.next;42 43 }44 45 public void binaryInsert(List<ListNode> lists, ListNode node){46 int start = 0;47 int end = lists.size()-1;48 int index = -1;49 while (start<end){50 int mid = (start+end)/2;51 if (node.val == lists.get(mid).val){52 index = mid;53 break;54 }55 56 if (node.val>lists.get(mid).val){57 start = mid+1;58 continue;59 }60 61 if (node.val<lists.get(mid).val){62 end = mid-1;63 continue;64 }65 }66 67 //NOTE: There are two ending cases, we need consider them carefully!.68 if (index==-1){69 if (start==end)70 if (node.val>lists.get(start).val) index=start+1;71 else index = start;72 else index = start; //i.e., start>end.73 } 74 75 lists.add(index,node);76 77 return;78 } 79 }
Leetcode-Merge k Sorted Lists
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。