题解 | #单链表的排序#
单链表的排序
https://www.nowcoder.com/practice/f23604257af94d939848729b1a5cda08
/** * struct ListNode { * int val; * struct ListNode *next; * }; */ /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 the head node * @return ListNode类 */ #include <stdbool.h> #include <stdlib.h> struct ListNode* sortInList(struct ListNode* head ) { // write code here struct ListNode* headlist[19]; struct ListNode* endlist[19]; struct ListNode* rtn = malloc(sizeof(struct ListNode)); struct ListNode* tmp = head; bool flag = true; rtn->next = NULL; rtn->val = 0; int i = 0; for(i = 0;i<19;i++){ headlist[i] = NULL; endlist[i] = NULL; } int count = 1; while(flag){ flag = false; rtn->next = NULL; while(tmp!=NULL){ int index = tmp->val / count; if(index!=0){ flag = true; } index = index%10; if(headlist[index+9] == NULL){ headlist[index+9] = tmp; }else{ endlist[index+9]->next = tmp; } endlist[index+9] = tmp; tmp = tmp->next; endlist[index+9]->next = NULL; } int last = 0; for(i = 0;i<19;i++){ if(headlist[i]!=NULL){ if(rtn->next == NULL){ rtn->next = headlist[i]; }else{ endlist[last]->next = headlist[i]; endlist[last] = NULL; } last = i; headlist[i] = NULL; } } endlist[last] = NULL; tmp = rtn->next; count = count*10; } return rtn->next; }