题目： https://leetcode-cn.com/problems/merge-k-sorted-lists/ 代码： /**
Definition for singly-linked list.struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; */ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode *pl1 = l1; ListNode *pl2 = l2; ListNode head(0); ListNode *phead = &head; while (pl1 != NULL&&pl2 != NULL) { if (pl1->val < pl2->val) { phead->next = pl1; phead = phead->next; pl1 = pl1->next; } else { phead->next = pl2; phead = phead->next; pl2 = pl2->next; } } if (pl1 == NULL) { phead->next = pl2; } if (pl2 == NULL) { phead->next = pl1; } return head.next;}
class Solution { public: ListNode* mergeKLists(vector<ListNode*>& lists) {
if (lists.empty()) return NULL; int size = lists.size(); if (size == 1) { return lists[0]; } if (size == 2) { return mergeTwoLists(lists[0], lists[1]); } int mid = size / 2; vector<ListNode *> sublist0; vector<ListNode *> sublist1; for (int i = 0; i < mid; i++) { sublist0.push_back(lists[i]); } for (int i = mid ; i < size; i++) { sublist1.push_back(lists[i]); } ListNode * l0 = mergeKLists(sublist0); ListNode *l1 = mergeKLists(sublist1); return mergeTwoLists(l0, l1);} };
结果：
