排序单向链表(妙)[递归]

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

输入: 4->2->1->3
输出: 1->2->3->4
示例 2:

输入: -1->5->3->4->0
输出: -1->0->3->4->5

思路：
1、确定链表的中点以便进行两路归并；
2、两路归并

中点的确认用的是快慢指针的方法，快指针走两步，慢指针走一步。在链表遍历完以后，慢指针指向的位置就是中点；<br />    链表的遍历是通过长度来确定的，确认完中点以后，需要切开链表，需要用变量保存中间节点的前驱，用来切断链表。<br />    确定链表中点以及切断链表的方法：<br />    ListNode * p_mid;<br />    ListNode * p_slow = head;<br />    ListNode * p_fast = head;<br />    while(p_fast && p_fast->next)<br />    {<br />        p_mid = p_slow;<br />        p_slow = p_slow->next;<br />        p_fast = p_fast->next->next;<br />    }<br />    p_mid->next = NULL;

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

ListNode* mergeSort(ListNode* pre, ListNode* behind){
    ListNode header(-1);
    ListNode *p = &header;
    while(pre && behind)
    {
        if(pre->val < behind->val){
            p->next = pre;
            pre = pre->next;
        }
        else
        {
            p->next = behind;
            behind = behind->next;
        }
        p = p->next;
    }
    p->next = (pre == NULL ? behind : pre);

    // 返回归并后子链表头结点
    return header.next;
}

ListNode* sortList(ListNode* head) {
    if (head == NULL || head->next == NULL)
        return head;
    ListNode * p_mid;               // 指向中结点
    ListNode * p_slow = head;       // 慢指针
    ListNode * p_fast = head;       // 快指针
    while(p_fast && p_fast->next)
    {
        p_mid = p_slow;
        p_slow = p_slow->next;
        p_fast = p_fast->next->next;
    }
    p_mid->next = NULL;
    // 吊炸天(骚气)的递归 
    return mergeSort(sortList(head), sortList(p_slow));
}