分治法。 這道題我是先用自己的方法做了出來，花費了很多時間，調(diào)試了很多次。最后和網(wǎng)上的解法對比了一下，發(fā)現(xiàn)自己的合并兩個鏈表的函數(shù)太繁雜，包含太多if else，典型的初學者思維，代碼不簡潔還容易出錯。所以網(wǎng)友的方法是在是值得學習，建議記下來，這是公式化的合并雙鏈表法。
我的C++代碼：
/** * Definition of ListNode * class ListNode { * public: * int val; * ListNode *next; * ListNode(int val) { * this->val = val; * this->next = NULL; * } * } */class Solution {public: /** * @param lists: a list of ListNode * @return: The head of one sorted list. */ ListNode *mergeKLists(vector<ListNode *> &lists) { int len = lists.size(); if (len == 0) { return NULL; } return mLists(lists,0,len-1); } ListNode *mLists(vector<ListNode*> &lists, int left, int right) { if (left == right) { return lists[left]; } if (right - left == 1) { return merge(lists[left],lists[right]); } ListNode * temp1 = mLists(lists,left,(left+right)/2); ListNode * temp2 = mLists(lists,(left+right)/2+1, right); return merge(temp1, temp2); } ListNode *merge(ListNode* l, ListNode *r) { ListNode * root = NULL,*temp=NULL; if (l==NULL && r==NULL) { return root; } if (l==NULL) { temp = new ListNode(r->val); root = temp; r = r->next; } else if (r == NULL) { temp = new ListNode(l->val); root = temp; l=l->next; } else if (l->val > r->val) { temp = new ListNode(r->val); r= r->next; root = temp; } else { temp = new ListNode(l->val); l = l->next; root = temp; } while(l!=NULL || r!=NULL) { if (l==NULL) { while (r!=NULL) { temp->next = new ListNode(r->val); r = r->next; temp = temp->next; } }else if (r==NULL) { while (l!=NULL) { temp->next = new ListNode(l->val); l = l->next; temp = temp->next; } } else if (l->val > r->val) { temp->next = new ListNode(r->val); r= r->next; temp = temp->next; } else { temp->next = new ListNode(l->val); l = l->next; temp = temp->next; } } return root; }};網(wǎng)友的C++代碼，他用了自底向上的迭代（我的是遞歸）：
class Solution {public: ListNode *mergeKLists(vector<ListNode *> &lists) { if (lists.size() == 0) return NULL; int n = lists.size(); while (n > 1) { int k = (n + 1) / 2; for (int i = 0; i < n / 2; ++i) { lists[i] = mergeTwoLists(lists[i], lists[i + k]); } n = k; } return lists[0]; } ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) { ListNode *head = new ListNode(-1); ListNode *cur = head; while (l1 && l2) { if (l1->val < l2->val) { cur->next = l1; l1 = l1->next; } else { cur->next = l2; l2 = l2->next; } cur = cur->next; } if (l1) cur->next = l1; if (l2) cur->next = l2; return head->next; }};除了上面的合并方法，其他合并雙鏈表的方法：
1.
class Solution {public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if (!l1) return l2; if (!l2) return l1; if (l1->val < l2->val) { l1->next = mergeTwoLists(l1->next, l2); return l1; } else { l2->next = mergeTwoLists(l1, l2->next); return l2; } }};2.
class Solution {public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if (!l1) return l2; if (!l2) return l1; ListNode *head = l1->val < l2->val ? l1 : l2; ListNode *nonhead = l1->val < l2->val ? l2 : l1; head->next = mergeTwoLists(head->next, nonhead); return head; }};新聞熱點
疑難解答
