題目

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

方法

使用歸並排序的思想，兩兩合並，直到最終變成一個。

		    public ListNode mergeKLists(ArrayList 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);
		    }