题解 | #单链表的排序#

核心思想

实质是数组归并排序思想

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */

/**
 * 
 * @param head ListNode类 the head node
 * @return ListNode类
 */
struct ListNode* sortInList(struct ListNode* head ) {
    // write code here
    // 归并排序
    // 递归分解
    // 后续再合并
    // case1: NULL list
    if(head == NULL)
    {
        return head;
    }
     
    // 递归终结条件,找到尾结点
    if(head->next == NULL)
    {
        return head;
    }
    
    // 快慢指针方法找到中间节点
    struct ListNode * fast = head->next, * slow = head;
    while(fast != NULL && fast->next != NULL)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
     
    struct ListNode * middle = slow->next;
    struct ListNode * left = NULL, * right = NULL;
    slow->next = NULL;
     
    left = sortInList(head);
    right = sortInList(middle);
    struct ListNode * newHead = NULL;
    struct ListNode * newTail = NULL;
 
    struct ListNode newNode = {0};
    newNode.next = NULL;
    newHead = &newNode;
    newTail = newHead;
    while(left != NULL && right != NULL)
    {
        if(left->val < right->val)
        {
            newTail->next = left;
            left = left->next;
        }
        else
        {
            newTail->next = right;
            right = right->next;
        }
        newTail = newTail->next;
        newTail->next =NULL;
    }
     
    if(left == NULL)
    {
        newTail->next = right;
    }
    if(right == NULL)
    {
        newTail->next = left;
    }
     
    return newHead->next;
}