首页 > 代码库 > Merge k Sorted Lists
Merge k Sorted Lists
题目
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
方法
使用归并排序的思想,两两合并,直到最终变成一个。public ListNode mergeKLists(ArrayList<ListNode> lists) { int len = lists.size(); if(len == 0){ return null; } int n = ( len + 1 ) / 2; while(len > 1){ for(int i = 0; i < n ; i++){ if(n + i < len){ if(lists.get(i) == null){ lists.set(i, lists.get(n + i)); lists.remove(n + i); }else if(lists.get(n + i) == null){ lists.remove(n + i); }else{ ListNode first = lists.get(i); ListNode second = lists.get(n + i); ListNode head = null; ListNode currentNode = null; ListNode node; while(first != null && second != null){ if(first.val < second.val){ node = first; first = first.next; }else{ node = second; second = second.next; } if(head == null){ head = node; currentNode = head; }else{ currentNode.next = node; node.next = null; currentNode = node; } } if(first != null){ currentNode.next = first; }else{ currentNode.next = second; } lists.set(i, head); lists.remove(n + i); } } len = lists.size(); n = (len + 1) / 2; } } return lists.get(0); }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。