题解 | #单链表的排序#
单链表的排序
https://www.nowcoder.com/practice/f23604257af94d939848729b1a5cda08?tpId=295&tqId=1008897&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
C语言
/** * * @param head ListNode类 the head node * @return ListNode类 */ //返回当前链表最小值的索引 int findListMinElem(struct ListNode* head){ int retMinIndex = 0, curIndex = 0; struct ListNode* tmpList = head; int minElem = tmpList->val; while(tmpList){ if(tmpList->val < minElem){ minElem = tmpList->val; retMinIndex = curIndex; } curIndex++; tmpList = tmpList->next; } return retMinIndex; } //大致思路：动态申请结果链表，依次遍历数组，找出最小的数，加到结果链表中 struct ListNode* sortInList(struct ListNode* head ) { // write code here struct ListNode* dummyHead = (struct ListNode*)malloc(sizeof(struct ListNode)); //虚拟头节点，用来指向实际头节点（因为头节点可能会被使用） dummyHead->next = head; struct ListNode* tmpList = head; struct ListNode* retCurNode; //用来指向返回链表的当前节点 struct ListNode* retListDummyHead = (struct ListNode*)malloc(sizeof(struct ListNode)); //结果链表 int listLen = 0, retListIndex = 0; //链表总长度 返回链表当前位置 int nowMinIndex; while(tmpList){ //获得链表的长度 tmpList = tmpList->next; listLen++; } retCurNode = retListDummyHead; while(retListIndex < listLen){ retCurNode->next = (struct ListNode*)malloc(sizeof(struct ListNode)); //为当前节点申请空间 retCurNode = retCurNode->next; nowMinIndex = findListMinElem(dummyHead->next); //找出当前剩余链表中，最小元素的索引 tmpList = dummyHead; for(int i=0; i<nowMinIndex; i++){ //找到当前链表中最小元素的前一个节点 tmpList = tmpList->next; } retCurNode->val = tmpList->next->val; //将最小元素保存到返回链表的当前节点中 tmpList->next = tmpList->next->next; //删除原始链表中最小元素的节点 retListIndex++; } retCurNode->next = NULL; return retListDummyHead->next; }