LeetCode: Merge k Sorted Lists [022]

【题目】

【题意】

合并K个有序链表

【思路】

【代码】

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* merge(vector
  
   &lists, int start, int end){
        if(start==end)return lists[start];
        int mid=(start+end)/2;
        ListNode*p1=merge(lists, start, mid);
        ListNode*p2=merge(lists, mid+1, end);
        ListNode*head=NULL, *p=NULL;
        while(p1&&p2){
            if(p1->val
   
    val){ if(p)p->next=p1; p=p1; p1=p1->next; } else{ if(p)p->next=p2; p=p2; p2=p2->next; } if(head==NULL)head=p; } if(p1){ if(p)p->next=p1; else{p=p1;head=p;} } if(p2){ if(p)p->next=p2; else{p=p2;head=p;} } return head; } ListNode *mergeKLists(vector
    
      &lists) { int size=lists.size(); if(size==0) return NULL; if(size==1) return lists[0]; return merge(lists, 0, size-1); } };