题解 | 单链表的排序

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 the head node
 * @return ListNode类
 */
#include <stdlib.h>
struct ListNode* sortInList(struct ListNode* head ) {
    // write code here
    if (head == NULL || head->next == NULL) {
        return head;
    }
    struct ListNode* slow = head;
    struct ListNode* fast = head->next;
    while (fast&&fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    struct ListNode* mid = slow->next;
    slow->next = NULL;
    struct ListNode* left = sortInList(head);
    struct ListNode* right = sortInList(mid);
    struct ListNode* res = (struct ListNode*)malloc(sizeof(struct ListNode));
    res->next = NULL;
    struct ListNode* curr = res;
    while (left&&right) {
        if (left->val>right->val) {
            curr->next = right;
            right = right->next;
        }
        else {
            curr->next = left;
            left = left->next;
        }
        curr=curr->next;
    }
    curr->next = left != NULL?left:right;
    return res->next;
}