首页 > 代码库 > leetcode. Merge k Sorted Lists
leetcode. Merge k Sorted Lists
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
类似归并排序，对于lists[0, n-1]，先对list[0,1], list[2, 3], ... list[n-2, n-1]排序，
然后在对生成新链表一次递归排序，需要调用两个已排序链表的merge函数。
1 ListNode *mergeKLists(vector<ListNode *> &lists) 2 { 3 if (lists.size() <= 0) 4 return NULL; 5 return merge_sort(lists, 0, lists.size() - 1); 6 } 7 8 ListNode *merge_sort(vector<ListNode *> &lists, int l, int r) 9 {10 ListNode *head;11 if (l < r)12 {13 int mid = (l + r) / 2;14 ListNode *left, *right;15 left = merge_sort(lists, l, mid);16 right = merge_sort(lists, mid + 1, r);17 head = merge(left, right);18 }19 else20 {21 head = lists[l];22 }23 return head;24 }25 26 ListNode *merge(ListNode *l1, ListNode *l2) 27 {28 ListNode *dummy1 = new ListNode(INT_MIN), *dummy2 = new ListNode(INT_MIN), *p, *r;29 dummy1->next = l1;30 dummy2->next = l2;31 32 p = dummy1;33 while (p->next != NULL && dummy2->next != NULL)34 {35 if (p->next->val > dummy2->next->val)36 {37 r = dummy2->next;38 dummy2->next = r->next;39 r->next = p->next;40 p->next = r;41 }42 p = p->next;43 }44 if (dummy2->next != NULL)45 {46 p->next = dummy2->next;47 dummy2->next = NULL;48 }49 p = dummy1->next;50 delete dummy1;51 delete dummy2;52 return p;53 }
leetcode. Merge k Sorted Lists
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。