合并K个已经排序的链表

mergeklists.md

Merge k Sorted Lists

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

时间复杂度为O(n),n代表链表总节点数

	/**
	 * Definition for singly-linked list.
	 * struct ListNode {
	 *     int val;
	 *     ListNode *next;
	 *     ListNode(int x) : val(x), next(NULL) {}
	 * };
	 */
	class Solution {
	public:
	    ListNode *mergeKLists(vector<ListNode *> &lists) {
	        /*
	        empty
	        */
	        if(lists.size() <= 0){
	            return nullptr;
	        }
	        /*
	        only one list
	        */
	        if(lists.size() == 1){
	            return lists[0];
	        }
	        /*
	        merged head
	        */
	        ListNode *mergedHead = lists[0];
	        /*
	        merge every two-list
	        */
	        for(int i=1;i<lists.size();i++){
	            mergedHead = mergeTwo(lists[i],mergedHead);
	        }
	        return mergedHead;
	    }
	    ListNode *mergeTwo(ListNode *list1,ListNode *list2){
	        /*
	        if one list empty,return the other one
	        */
	        if(!list1){
	            return list2;
	        }else if(!list2){
	            return list1;
	        }
	        /*
	        merged head
	        */
	        ListNode *mergedHead = nullptr;
	        /*
	        recursively
	        */
	        if(list1->val < list2->val){
	            mergedHead = list1;
	            mergedHead->next = mergeTwo(list1->next,list2);
	        }else{
	            mergedHead = list2;
	            mergedHead->next = mergeTwo(list1,list2->next);
	        }
	        return mergedHead;
	    }
	};