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;
28: head = head->next;
29: delete del;
30: return head;
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;
14: while(head1!=NULL && head2!=NULL)
15: {
16: if(head1->val < head2->val)
17: {
18: p->next = head1;
19: head1 = head1->next;
20: }
21: else
22: {
23: p->next = head2;
24: head2 = head2->next;
25: }
26: p = p->next;
27: }
28: if(head1 !=NULL)
29: {
30: p->next = head1;
31: }
32: if(head2 != NULL)
33: {
34: p->next = head2;
35: }
36: p = head;
37: head = head->next;
38: delete p;
39: return head;
40: }
No comments:
Post a Comment