题解 | #单链表的排序#

struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    struct ListNode* yhead = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* cur = yhead;

    while (pHead1 && pHead2) {
        if (pHead1->val <= pHead2->val) {
            cur->next = pHead1;
            pHead1 = pHead1->next;
        } else {
            cur->next = pHead2;
            pHead2 = pHead2->next;
        }
        cur = cur->next;
    }
    cur->next = pHead1 ? pHead1 : pHead2;
    return yhead->next;
}

struct ListNode* sortInList(struct ListNode* head ) {
    if (!head || !head->next)  return head;
    struct ListNode* left = head;
    struct ListNode* mid = head->next;
    struct ListNode* right = head->next->next;

    while (right && right->next) {
        left = left->next;
        mid = mid->next;
        right = right->next->next;
    }
    left->next = NULL;
    return Merge(sortInList(head), sortInList(mid));
}