题解 | #合并k个已排序的链表#
合并k个已排序的链表
https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6
二路归并排序思想用一下结束
/** * struct ListNode { * int val; * struct ListNode *next; * }; */ /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param lists ListNode类一维数组 * @param listsLen int lists数组长度 * @return ListNode类 */ #include <malloc.h> struct ListNode* merge(struct ListNode* head1,struct ListNode* head2){ struct ListNode* p = head1; struct ListNode* q = head2; //哑变量 struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode)); dummy->next = NULL; struct ListNode* temp = dummy; //合并 while(p!=NULL&&q!=NULL){ if(p->val>q->val){ temp ->next = q; q = q ->next; }else{ temp ->next = p; p = p->next; } temp = temp->next; } while(p!=NULL){ temp->next = p; p = p->next; temp = temp->next; } while(q!=NULL){ temp->next = q; q = q->next; temp = temp->next; } temp = NULL; return dummy->next; } /*递归merge*/ struct ListNode* mergeSort(struct ListNode** lists, int left,int right){ if(left>=right){ return lists[left]; } int mid = (left+right)/2; struct ListNode* ll = mergeSort(lists,left,mid); struct ListNode* lr = mergeSort(lists, mid +1,right); return merge(ll,lr); } struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) { // write code here return mergeSort(lists,0,listsLen-1); }