数据结构链表学习Day?--合并K个升序链表

数据结构链表学习Day?--合并K个升序链表

23. 合并K个升序链表

我觉得这个题最好的做法是用分治法：
过程：

将整个链表合并可以分解成：
1.将数组的左半边合并。
2.将数组的右半边合并。
3.最终将数组的左右两边合并。

其中需要掌握将两个有序递增链表合并的知识。

class Solution {
public:
	//3.合并两个有序递增链表的逻辑 (相当于最后一步将左右半边合并)
    ListNode* mergeTwoLists(ListNode *a, ListNode *b) {
        if ((!a) || (!b)) return a ? a : b;
        ListNode head, *tail = &head, *aPtr = a, *bPtr = b;
        while (aPtr && bPtr) {
            if (aPtr->val < bPtr->val) {
                tail->next = aPtr; aPtr = aPtr->next;
            } else {
                tail->next = bPtr; bPtr = bPtr->next;
            }
            tail = tail->next;
        }
        if(aPtr){
        	tail->next=aPtr;
        }
        else{
        	tail->next=bPtr;
        }
        return head.next;
    }
	//2、将整个数组的左半边、右半边分别合并。
    ListNode* merge(vector  &lists, int l, int r) {
        if (l == r) return lists[l];
        if (l > r) return nullptr;
        int mid = (l + r) / 2;
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }
	//1、起始函数：
    ListNode* mergeKLists(vector& lists) {
        return merge(lists, 0, lists.size() - 1);
    }
};

注意用分治法的时候函数的定义，一般都是这种借助递归来实现大规模问题小规模化。

    ListNode* mergeKLists(vector& lists) {
        return merge(lists, 0, lists.size() - 1);
    }

分治法的复杂度的求解也很重要