题解 | #合并k个已排序的链表#
合并k个已排序的链表
https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6
struct ListNode* merge(struct ListNode* head1, struct ListNode* head2) { struct ListNode *p = head1; struct ListNode *q = head2; if(p == NULL){ return q; }else if(q == NULL){ return p; }else if(p->val < q->val){ p->next = merge(p->next, q); return p; }else{ q->next = merge(p, q->next); return q; } } struct ListNode* toSortList(struct ListNode* head, struct ListNode* tail) { if (head == NULL) { return head; } if (head->next == tail) { head->next = NULL; return head; } struct ListNode *slow = head, *fast = head; while (fast != tail) { slow = slow->next; fast = fast->next; if (fast != tail) { fast = fast->next; } } struct ListNode* mid = slow; return merge(toSortList(head, mid), toSortList(mid, tail)); } struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) { if(listsLen == 0) return NULL; struct ListNode *dummy = (struct ListNode*)malloc(sizeof(struct ListNode)); dummy->val = 0;//初始化 struct ListNode *pr = dummy; for(int i = 0; i < listsLen; i++){ pr->next = lists[i]; while(pr->next != NULL){ pr = pr->next; } } //排序 return toSortList(dummy->next, NULL); }