题解 | #单链表的排序#

归并排序

1 利用快慢指针寻找中心点

2 递归分成不能再分的小区域

3 建立新链表利用比较法依次插入

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

class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    ListNode* mergeSort(ListNode* head)
    {
        if(!head||!head->next)    return head;
      //寻找中心点
        ListNode *fast = head, *slow = head;
        while(fast->next && fast->next->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode* newList = slow->next;
        slow->next = NULL;
      //递归调用 寻找归并区间
        ListNode* left = mergeSort(head);
        ListNode* right = mergeSort(newList);
        return linkList(left, right);
    }
    //建立新链表 并插入
    ListNode* linkList(ListNode* left, ListNode* right)
    {
        ListNode* p = new ListNode(0);
        ListNode* temp = p;
        while(left && right)
        {
            if(left->val<=right->val)
            {
                temp->next = left;
                left = left->next;
                temp = temp->next;
            }
            else{
                temp->next = right;
                right = right->next;
                temp = temp->next;
            }
        }
        if(left)
            temp->next = left;
        else
            temp->next = right;
        return p->next;
    }
    ListNode* sortInList(ListNode* head) {
        // write code here
        if(!head)    return NULL;
        else    return mergeSort(head);
    }
};