A solution to merge k sorted linked list beat all solutions


  • 0
    L
    class Solution {
    public:
    	ListNode *mergeKLists(vector<ListNode *> &lists) {
    		ListNode* head = NULL;
    		int sz = lists.size();
    		if (sz){
    			return BinaryMergeList(lists, 0, sz - 1);
    		}
    		return head;
    	}
    private:
    	ListNode* copy(ListNode* node){
    		if (node)
    			return new ListNode(node->val);
    		else
    			return NULL;
    	}
    	ListNode* BinaryMergeList(vector<ListNode*>& lists, int start, int end){
    		if (start > end){
    			return NULL;
    		}
    		else if (start == end){
    			return lists[start];
    		}
    		else if (start == end - 1){
    			return mergeTwoList(lists[start], lists[end]);
    		}
    		else{
    			int middle = (start + end) >> 1;
    			return mergeTwoList(BinaryMergeList(lists,start,middle),BinaryMergeList(lists,middle+1,end));
    		}
    	}
    	ListNode* mergeTwoList(ListNode* first, ListNode* second){
    		ListNode* head = NULL;
    		if (!first && second){
    			head = second;
    		}
    		else if (first && !second){
    			head = first;
    		}
    		else if(first && second){
    			if (first->val <= second->val){
    				head = first;
    				first = first->next;
    			}
    			else{
    				head = second;
    				second = second->next;
    			}
    			ListNode* cur = head;
    			while (first && second){
    				if (first->val <= second->val){
    					cur->next = first;
    					cur = first;
    					first = first->next;
    				}
    				else{
    					cur->next = second;
    					cur = second;
    					second = second->next;
    				}
    			}
    			if(first){
    			    cur->next = first;
    			}
    			if(second){
    			    cur->next = second;
    			}
    		}
    		return head;
    	}
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.