原题链接：http://oj.leetcode.com/problems/merge-k-sorted-lists/

题目描述：

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

题解：

　　这是个典型的分治题，用递归，不断平分，解决merge两个有序链表的小问题即可。

1 /** 2  * Definition for singly-linked list. 3  * struct ListNode { 4  *     int val; 5  *     ListNode *next; 6  *     ListNode(int x) : val(x), next(NULL) {} 7  * }; 8  */ 9 class Solution {10 public:11     ListNode *merge(ListNode* A,ListNode* B){12         if(A==NULL && B==NULL)13             return NULL;14         if(A == NULL)15             return B;16         if(B == NULL)17             return A;18         ListNode *p = A;19         ListNode *q = B;20         ListNode *res = NULL;21         ListNode *pre = NULL;22         if(p->val<=q->val){23             res = p;24             p = p->next;25             pre = res;26         }else{27             res = q;28             q = q->next;29             pre = res;30         }31         while(p!=NULL && q!=NULL){32             if(p->val<=q->val){33                 pre->next = p;34                 pre = p;35                 p = p->next;36             }else{37                 pre->next = q;38                 pre = q;39                 q = q->next;40             }41         }42         while(p!=NULL){43             pre->next = p;44             pre = p;45             p = p->next;46         }47         while(q!=NULL){48             pre->next = q;49             pre = q;50             q = q->next;51         }52         pre->next = NULL;53         return res;54     }55     56     ListNode *mergeKLists(vector
     
       &lists) {57         int size = lists.size();58         if(size == 0)59             return NULL;60         if(size == 1)61             return lists[0];62         vector
      
        A,B;63         for(int i=0; i