题解 | #单链表的排序#

这题我们主要的思路是：先将链表中的所有的元素值取出存入数组中，然后对该数组进行排序，在遍历数组将元素依次存入每个结点的val值中

ps：这题我主要是看见一个人的思路点拨，感觉很巧妙：将数据取出在排序，之后修改结点的值，而不进行结点位置的重新插入

class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    ListNode* sortInList(ListNode* head) {
        // write code here
        //将所有的链表元素的值取出放入一个数组，然后对数组的元素排序后在依次放入单链表
        ListNode* p=head;
        vector<int> vec;
        while(p)
        {
            vec.push_back(p->val);
            p=p->next;
        }
        sort(vec.begin(), vec.end());
        p=head;
        for(int i=0;i<vec.size();i++)
        {
            p->val=vec[i];
            p=p->next;
        }
        return head;
        
        
    }
};