[23] Merge k Sorted Lists

好吧就把今日命名為湊題數之日好了.....

湊著湊著湊了一個hard , 而我懶得再去看更多解法了(被歐飛）

簡單說就是先把mergeTwoLists 再寫一遍然後拿來用QQ

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* struct ListNode *next;

* };

*/

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){

if (list1== NULL)

return list2;

if (list2==NULL)

return list1;

struct ListNode *p1,*p2, *head,*now;

p1=list1;

p2=list2;

if (p1->val < p2->val )

{

head = p1;

p1=p1->next;

}

else

{

head = p2;

p2=p2->next;

}

now = head;

while (p1!=NULL && p2!=NULL)

{

if (p1->val < p2->val )

{

now->next = p1;

p1=p1->next;

}

else

{

now->next = p2;

p2=p2->next;

}

now=now->next;

}

if (p1==NULL)

now->next =p2;

else

now->next = p1;

return head;

}

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* struct ListNode *next;

* };

*/

struct ListNode* mergeKLists(struct ListNode** lists, int listsSize){

if (listsSize==1)

return lists[0];

struct ListNode* new = NULL;

for (int i=0;i<listsSize-1;i++)

{

new = mergeTwoLists(lists[i],lists[i+1]);

lists[i+1]=new;

}

return new;

}

20240811 更新

原來可以偷吃步嗎= = 說是把全部list 的number 存起來sort 後再生出一個return linked list 回去。當做練一下語感？！ ～___～ 不過新的head 寫在迴圈裡覺得好醜喔。

本來是想要拿掉TBD的，結果要用C 沒有的priority queue 嗎XD （max heap)

算了啦算了啦（自暴自棄貌）怎麼那麼喜歡heap 啊！！！

int comp(const void *a, const void *b)

{

return (*(int*)a - *(int*)b);

}

struct ListNode* mergeKLists(struct ListNode** lists, int listsSize){

int *nums = calloc (10000, sizeof(int));

int count = 0;

struct ListNode* ptr ;

for (int i=0; i<listsSize; i++)

{

ptr = lists[i];

while (ptr != NULL)

{

nums[count++]= ptr->val;

ptr = ptr->next;

}

}

qsort (nums, count, sizeof(int), comp);

struct ListNode* head = NULL;

ptr = head;

for (int i=0; i<count; i++)

{

struct ListNode *new = calloc (1, sizeof(struct ListNode));

new->val = nums[i];

new->next = NULL;

if (head == NULL)

{

head = new;

ptr = head;

}

else

{

ptr->next = new;

ptr = ptr->next;

}

}

return head;

}