排序链表

题目链接：https://leetcode-cn.com/problems/sort-list/
题目解题：
方法一：归并排序

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:

    /***两个有序链表合并***/
   ListNode* mergeList(ListNode* l1, ListNode* l2)
   {
       ListNode *dummy = new ListNode(0);
       ListNode *p = dummy;
        while(l1 != nullptr && l2 != nullptr)
        {
            if(l1->val > l2->val)
            {
                p->next = l2;
                l2 = l2->next;
            }else{
                p->next = l1;
                l1 = l1->next;
            }
            p = p->next;
        }
        p->next = (l1 == nullptr ? l2 : l1);
        return dummy->next;
   }
   ListNode* sortList(ListNode* head, ListNode* tail)
   {
        if(head == nullptr)
            return head;
        if(head->next == tail)
        {
            head->next = nullptr;
            return head;
        }
        //快慢指针寻找中间位置
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast != tail && fast->next != tail)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode *mid = slow;
        return mergeList(sortList(head, mid), sortList(mid, tail));

   }

    ListNode* sortList(ListNode* head) {
        return sortList(head, nullptr);

    }
};

方法二：
1.将链表的每个节点先存入vector中，
2.对vector进行排序
3.再将排序的值链成链表。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    bool static compare(ListNode* node1, ListNode* node2)
    {
        return node1->val < node2->val ;
    }

    ListNode* sortList(ListNode* head) {
        vector<ListNode*> vec;
        if(!head || !head->next)
            return head;
        while(head != nullptr)
        {
            vec.push_back(head);
            head = head->next;
        }
        sort(vec.begin(), vec.end(),compare);
        ListNode* dummy = new ListNode(0);
        dummy->next = vec[0];
        for(int i = 0; i < vec.size() -1; ++i)
        {
            vec[i]->next = vec[i + 1];
            vec[i + 1]->next = nullptr;
        }
        return dummy->next;


    }
};