牛客网：单链表的排序

嘛，归并就完事：

关键是好像不如数组的归并方便对吧。但是思路是一样的，先将链表拆分成两半，然后不断拆分，最后拆分完了就向上归并，代码如下所示：

class Solution {
public:
    
    ListNode* merge(ListNode *pHead1, ListNode *pHead2){
        if(pHead1 == NULL) return pHead2;
        if(pHead2 == NULL) return pHead1;
        ListNode *p=NULL;
        if(pHead1->val <= pHead2->val){
            p = pHead1;
            p->next = merge(pHead1->next, pHead2);
        }else{
            p = pHead2;
            p->next = merge(pHead1, pHead2->next);
        }
        return p;
    }
    
    ListNode* sortInList(ListNode* head) {
        // 链表为空或者只有一个节点 直接就是有序的
        if(head==NULL || head->next==NULL){
            return head;
        }
        ListNode *left = head;
        ListNode *mid = head->next;
        ListNode *right = head->next->next;
        while(right!=NULL && right->next!=NULL){
            left=left->next;
            mid=mid->next;
            right=right->next->next;
        }
        left->next=NULL;
        return merge(sortInList(head), sortInList(mid));
    }
};