题解 | #单链表的排序#

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

#include <vector>
class Solution {
  public:
    /**
     *
     * @param head ListNode类 the head node
     * @return ListNode类
     */

    vector<int> arr;
    int partition(int left, int right) {
        // cout<<left<<right<<"oo";
        int pivot;
        pivot = arr[left];
        while (left < right) {

            while (left < right && arr[right] >= pivot) {
                right--;
            }
            arr[left] = arr[right];
            while (left < right && arr[left] < pivot) {
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = pivot;
        cout << endl;
        return left;
    }
    void mySort(int l, int r) {
        if (l < r) {
            int mid = partition(l, r);
            mySort(l, mid - 1);
            mySort(mid + 1, r);
        }
    }
    ListNode* sortInList(ListNode* head) {
        // write code here
        arr.resize(100000);
        ListNode* p = head;
        int len = 0;
        while (p) {
            arr[len] = p->val;
            p = p->next;
            len++;
        }
        mySort(0, len - 1); //对arr排序
        p = head;
        int idx = 0;
        while (p) {
            p->val = arr[idx++];
            p = p->next;
        }
        return head;
    }
};