题解 | #合并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"string.h" #include <math.h> #define CompareNode(a,b) (a->val<b->val) //在一个排序链表里面插入一个新节点 struct ListNode* InserNewNodetList(struct ListNode* head,struct ListNode*new) { struct ListNode* p=head; if(CompareNode(new,head)==1) { new->next=head; return new; } while(p->next){ if(CompareNode(new,p->next)==1){ new->next=p->next; p->next=new; return head; } p=p->next; } p->next=new; //插入链表最后 new->next=NULL; return head; } //两个链表合并成一个排序的链表 ,返回排序链表的指针 struct ListNode* SortList(struct ListNode*a ,struct ListNode*b) { struct ListNode* pa=a,*pb=b,*pbuf; if(pb==NULL||pa==NULL) return (pa==NULL ? pb:pa); while(pb){ pbuf=pb; pb=pb->next; pa=InserNewNodetList(pa,pbuf); //从b链表里面取元素依次插入a链表 } return pa; } struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) { // write code here struct ListNode* pa=NULL; int i=1; pa=lists[0]; while(i<listsLen){ pa= SortList(pa,lists[i]); i++; } return pa; }