题解 | #单链表的排序#

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

class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
     // 二元谓词
    class shengxu{
        // 谓词的作用域注意是在public下
    public:
        bool operator()(ListNode* node1, ListNode* node2){
            return node1->val < node2->val;
        }
    };  // 类的最后要加 ;
    ListNode* sortInList(ListNode* head) {
        if(!head) return NULL;  // 如果链表为空，返回NULL
        // 创建新结点，使其等于head
        ListNode* pre  = head;
        // 创建vector容器，存储链表中的结点
        vector<ListNode*> vec;
        while(pre){
            vec.push_back(pre);
            pre = pre->next;
        }
        sort(vec.begin(), vec.end(), shengxu());    // 利用谓词，对结点升序排列
	  // 创建头尾结点，将vector容器中的结点依次插入其中
        ListNode* temp = vec[0];
        ListNode* result = temp;
        ListNode* tail = NULL;
        temp->next = tail;
        for(int j = 1; j < vec.size(); ++j){
            temp->next = vec[j];
            vec[j]->next = tail;
            temp = temp->next;	// 注意更新temp结点的位置
        }
        return result;
    }
};