题解 | #单链表的排序#

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;
}