题解 | #合并k个已排序的链表#

这个题属于一个递归分治的思想（这是我觉得啊）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
  public:
    ListNode* mergeNode(ListNode* node1, ListNode* node2) {  //@1:
        if(node1 == NULL) return node2;
        if(node2 == NULL) return node1;

        ListNode* Head = new ListNode(-1);

        ListNode* curNode = Head ;

        while (node1 && node2) {
            if(node1->val <= node2->val){
                curNode->next = node1;
                node1 = node1->next;
            }else{
                curNode -> next = node2;
                node2 = node2->next;
            }
            curNode = curNode->next;
        }
        if(node1) curNode->next = node1;
        else curNode->next = node2;
        return Head->next;
    }

    ListNode* dievideMerge(vector<ListNode*> &lists, int left , int right){  //@2:
        if(left > right)    return NULL;
        else if (left == right) return lists[left];
        int mid = (left + right) / 2;
        return mergeNode(dievideMerge(lists, left, mid), dievideMerge(lists, mid + 1 , right));  //@3:
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return dievideMerge(lists, 0, lists.size() - 1);

    }
};

//@1：很经典的双有序链表合并，这个在做这个题之前应该做过了，不讲了
//@2: 这个函数主要是用来分隔分治的，将一段链表列表分成多个双链表，然后进行合并
//@3: 这里是递归分治，通过不断二分递归（比如，第一次递归将列表分为左右两个，第二次就把左边的那部分再分成左右两部分...），最后递归到底就是两个两个合并了。