题解 | #单链表的排序#

单链表排序，采用最简单的方法，建立一个数组，遍历链表，将每个结点的值存入数组，对数组排序，再将排序后的数组的值依次赋值给每个结点。完整代码如下。

class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    ListNode* sortInList(ListNode* head) {
        // write code here
        ListNode *p = head;
        int count = 0;
        //获取结点个数
        while(p != NULL){
            count++;
            p = p->next;
        }
        int valArr[count];
        p = head;
        //将每个结点的值存入数组
        for(int i = 0;i < count;i++){
            valArr[i] = p->val;
            p = p->next;
        }
        //对数组进行排序，这里使用简单的冒泡排序。若追求效率可选用其他排序。
        for(int i = 0;i < count - 1;i++){
            for(int j = 0;j < count - i - 1 ;j++){
                if(valArr[j] > valArr[j + 1]){
                    int temp = valArr[j];
                    valArr[j] = valArr[j + 1];
                    valArr[j + 1] = temp;
                }
            }
        }
        p = head;
        //依次对结点赋值
        for(int i = 0;i < count;i++){
            p->val = valArr[i];
            p = p->next;
        }
        return head;
    }
};