题解 | #单链表的排序#

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 the head node
 * @return ListNode类
 */
struct ListNode* sortInList(struct ListNode* head ) {
    // write code here
    if(head == NULL || head->next == NULL) return head;
    struct ListNode *right = head, *mid = head, *left = head;
    while(right && right->next) {
        right = right->next->next;
        if(right == NULL || right->next == NULL) {
            left = mid;
        }
        mid = mid->next;
    }
    left->next = NULL;
    left = sortInList(head);
    right = sortInList(mid);
    printf("left: %d\nright: %d\n", left->val, right->val);
    struct ListNode dummy;
    struct ListNode* cur = &dummy;
    while(left != NULL && right != NULL) {
        if(left->val <= right->val) {
            cur->next = left;
            left = left->next;
        } else {
            cur->next = right;
            right = right->next;
        }
        cur = cur->next;
    }
    if(left) {
        cur->next = left;
    } else if(right) {
        cur->next = right;
    }
    
    return dummy.next;
}