## Wednesday, December 26, 2012

### [LeetCode] Merge k Sorted Lists 解题报告

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
» Solve this problem

[解题思路]
merge sort。外面套一层循环即可。注意指针操作即可。

[Code]
``````1:    ListNode *mergeKLists(vector<ListNode *> &lists) {
2:      // Start typing your C/C++ solution below
3:      // DO NOT write int main() function
4:      ListNode * head = new ListNode(INT_MIN);
5:      for(int i = 0; i < lists.size(); i++)
6:      {
7:        ListNode* p1 = head->next;
8:        ListNode * p2 = lists[i];
9:        ListNode* pre = head;
10:        while(p1!= NULL && p2!= NULL)
11:        {
12:          if(p1->val >= p2->val)
13:          {
14:            pre->next = p2;
15:            p2 = p2->next; pre = pre->next;
16:            pre->next = p1;
17:            continue;
18:          }
19:          pre = p1;
20:          p1 = p1->next;;
21:        }
22:        if(p2 != NULL)
23:        {
24:          pre->next = p2;
25:        }
26:      }
27:      ListNode* del = head;
29:      delete del;
31:    }
``````

Update, 3/9/2013
Refactor the code
``````1:    ListNode *mergeKLists(vector<ListNode *> &lists) {
2:      if(lists.size() == 0) return NULL;
3:      ListNode *p = lists[0];
4:      for(int i =1; i< lists.size(); i++)
5:      {
6:        p = merge2Lists(p, lists[i]);
7:      }
8:      return p;
9:    }
10:    ListNode * merge2Lists(ListNode *head1, ListNode *head2)
11:    {
12:      ListNode *head = new ListNode(INT_MIN);
13:      ListNode *p = head;
15:      {
17:        {
18:          p->next = head1;
20:        }
21:        else
22:        {
23:          p->next = head2;
25:        }
26:        p = p->next;
27:      }
29:      {
30:        p->next = head1;
31:      }
32:      if(head2 != NULL)
33:      {
34:        p->next = head2;
35:      }
36:      p = head;