牛客题霸 单链表的选择排序 C++题解/答案

题目描述

给定一个无序单链表，实现单链表的选择排序(按升序排序)。

题解：

不可能手写排序，这辈子不可能手写排序。。
基础的链表操作，将链表内的数据存到vector内，然后用sort排序，再将vector内的数据存会数组即可

代码：

/** * struct ListNode { * int val; * struct ListNode *next; * }; */

class Solution {
   
public:
    /** * * @param head ListNode类 the head node * @return ListNode类 */
    ListNode* sortInList(ListNode* head) {
   
        if(!head||!head->next)return head;
        vector<int>vec;
        ListNode牛客题霸 单链表的选择排序 C++题解/答案 * p=head;
        while(p!=NULL)
            {
   
                vec.push_back(p->val);
            p=p->next;
            }
        sort(vec.begin(),vec.end());
        p=head;
        int k=0;
        while(p!=NULL)
        {
   
            p->val=vec[k];
            k++;
            p=p->next;
        }    
        return head;
    }
};