题解 | #合并k个已排序的链表#
合并k个已排序的链表
https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ #include <vector> class Solution { public: ListNode * Merge2(ListNode * pHead1,ListNode * pHead2){ if(pHead1 ==nullptr) return pHead2; if(pHead2 == nullptr) return pHead1; ListNode * head = new ListNode(0); ListNode * tail = head; while(pHead1 && pHead2){ if(pHead1->val < pHead2->val){ tail->next = pHead1; pHead1 = pHead1->next; } else{ tail->next = pHead2; pHead2 = pHead2->next; } tail = tail->next; } if(pHead1){ tail->next = pHead1; } else{ tail->next = pHead2; } return head->next; } ListNode * divideMerge(vector<ListNode *> &lists,int left,int right){ if(left > right) return nullptr; else if (left == right) return lists[left]; int mid = (left + right) >> 1; return Merge2(divideMerge(lists, left, mid),divideMerge(lists, mid+1, right)); } ListNode *mergeKLists(vector<ListNode *> &lists) { return divideMerge(lists,0,lists.size()-1); } };