[148] Sort List （TBD）

Linked list 的sorting ！感覺就是要用bubble sort啊！！！XD（誰規定的XD）

用bubble sort可以單純使用 int的swap就好，而不需要swap node (thinking 圖)

不出所料的超時了XD  （附在最後面）

於是用了copy成array再用qsort把值存回去的方法，是一個偷吃步 XD！

晚點再來看解答

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

{

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

}

struct ListNode* sortList(struct ListNode* head){

int len = 0;

struct ListNode* ptr=head;

int *tmparray=malloc(sizeof(int)*50000);

while (ptr != NULL)

{

tmparray[len++]= ptr->val;

ptr= ptr->next;

}

qsort ((void*)tmparray, len, sizeof(int), comp);

ptr = head;

len=0;

while (ptr != NULL)

{

ptr->val = tmparray[len++];

ptr= ptr->next;

}

return head;

}

結果是要用merge sort是嗎！！！（大驚）

用linked list 寫merge sort也太麻煩了吧 （有種妳在面試的時候這樣講啊XD）

那就先這樣好了.....(眼神游移）

Bubble sort : 

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* struct ListNode *next;

* };

*/

struct ListNode* sortList(struct ListNode* head){

int len = 0;

struct ListNode* ptr=head;

while (ptr != NULL)

{

ptr= ptr->next;

len++;

}

int ite=0;

for (ite=len-1; ite>=0;ite--)

{

ptr = head;

for (int j=ite; j>0;j--)

{

if (ptr->next == NULL)

break;

if (ptr->val > ptr->next->val)

{

int tmp = ptr->val;

ptr->val= ptr->next->val;

ptr->next->val=tmp;

}

ptr= ptr->next;

}

}

return head;

}