給你鏈表的頭結(jié)點(diǎn) head ，請將其按 升序 排列并返回 排序后的鏈表 。

示例 1：

輸入：head = [4,2,1,3]
輸出：[1,2,3,4]
示例 2：

輸入：head = [-1,5,3,4,0]
輸出：[-1,0,3,4,5]
示例 3：

輸入：head = []
輸出：[]

提示：

鏈表中節(jié)點(diǎn)的數(shù)目在范圍 [0, 5 * 104] 內(nèi)
-105 <= Node.val <= 105

進(jìn)階：你可以在 O(n log n) 時間復(fù)雜度和常數(shù)級空間復(fù)雜度下，對鏈表進(jìn)行排序嗎？

自解

自解大失敗，拼盡全力無法戰(zhàn)勝超時

//按順序排到新鏈表里，超時
struct ListNode dummy;
struct ListNode * s_insert(struct ListNode *newnode)
{
    struct ListNode *temp=NULL,*next=NULL,*head=&dummy;
    if(head->next==NULL)
    {
        dummy.next=newnode;
        next=newnode->next;
        newnode->next=NULL;
        return next;
    }
    
    while(head->next!=NULL&&head->next->val<newnode->val)
    {
        head=head->next;
    }
    temp=head->next;
    head->next=newnode;
    next=newnode->next;
    newnode->next=temp;
    return next;
}

struct ListNode* sortList(struct ListNode* head) {
    dummy.next=NULL;
    while(head!=NULL)
    {
        head=s_insert(head);
    }
    return dummy.next; 
}

 //雙指針冒泡排序,超時，實(shí)質(zhì)是對兩兩交換鏈表中的節(jié)點(diǎn)題加上了判斷條件
struct ListNode* sortList(struct ListNode* head) {
    if(head==NULL)return head;
    struct ListNode dummy;
    dummy.next=head;
    head=&dummy;
    struct ListNode *right=&dummy,*p=NULL;
    struct ListNode *temp=NULL,*temp1=NULL;
    while(head->next->next!=p)
    {
        while(right->next->next!=p)
        {
            if(right->next->val>right->next->next->val)
            {
                temp=right->next->next->next;
                right->next->next->next=right->next;
                temp1=right->next->next;
                right->next->next=temp;
                right->next=temp1;
            }
            right=right->next;
        }
        p=right->next;
        right=head;
    }
    return dummy.next;

}

力扣解

1.遞歸
將鏈表拆成一個個節(jié)點(diǎn)再合并

// 876. 鏈表的中間結(jié)點(diǎn)（快慢指針）
struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode* pre = head;
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while (fast && fast->next) {
        pre = slow; // 記錄 slow 的前一個節(jié)點(diǎn)
        slow = slow->next;
        fast = fast->next->next;
    }
    pre->next = NULL; // 斷開 slow 的前一個節(jié)點(diǎn)和 slow 的連接
    return slow;
}

// 21. 合并兩個有序鏈表（雙指針）
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    struct ListNode dummy; // 用哨兵節(jié)點(diǎn)簡化代碼邏輯
    struct ListNode* cur = &dummy; // cur 指向新鏈表的末尾
    while (list1 && list2) {
        if (list1->val < list2->val) {
            cur->next = list1; // 把 list1 加到新鏈表中
            list1 = list1->next;
        } else { // 注：相等的情況加哪個節(jié)點(diǎn)都是可以的
            cur->next = list2; // 把 list2 加到新鏈表中
            list2 = list2->next;
        }
        cur = cur->next;
    }
    cur->next = list1 ? list1 : list2; // 拼接剩余鏈表
    return dummy.next;
}

struct ListNode* sortList(struct ListNode* head) {
    // 如果鏈表為空或者只有一個節(jié)點(diǎn)，無需排序
    if (head == NULL || head->next == NULL) {
        return head;
    }
    // 找到中間節(jié)點(diǎn) head2，并斷開 head2 與其前一個節(jié)點(diǎn)的連接
    // 比如 head=[4,2,1,3]，那么 middleNode 調(diào)用結(jié)束后 head=[4,2] head2=[1,3]
    struct ListNode* head2 = middleNode(head);
    // 分治
    head = sortList(head);
    head2 = sortList(head2);
    // 合并
    return mergeTwoLists(head, head2);
}

作者：靈茶山艾府
鏈接：https://leetcode.cn/problems/sort-list/solutions/2993518/liang-chong-fang-fa-fen-zhi-die-dai-mo-k-caei/
來源：力扣（LeetCode）
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

仿解

看過答案自己寫的遞歸，非常慚愧，合并有序鏈表明明已經(jīng)做出來，卻又做錯，找了好一會錯誤

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *MiddleFind(struct ListNode *head)//找中間節(jié)點(diǎn)
{
    struct ListNode *fast=head,*slow=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
    }
    return slow;
}

struct ListNode *hebing(struct ListNode *list1,struct ListNode *list2)//合并有序節(jié)點(diǎn)
{
	struct ListNode dummy,*p=&dummy;
	while(list1&&list2)
	{
		if(list1->val<=list2->val)
		{
			p->next=list1;
			p=p->next; 
			list1=list1->next;
		}
		else
		{
			p->next=list2;
			p=p->next; 
			list2=list2->next;
		}
	}
	p->next=list1?list1:list2;
	return dummy.next;

}

struct ListNode* sortList(struct ListNode* head) {
    struct ListNode *temp=NULL,*temp1=NULL;
    if(head==NULL||head->next==NULL)//鏈表不可切割時停止遞歸直接返回
    {
        return head;
    }
    else
    {
        temp=MiddleFind(head);//找中間節(jié)點(diǎn)
        if(temp->next==NULL)//考慮只剩兩個節(jié)點(diǎn)的特殊情況，此時中間節(jié)點(diǎn)是最后一個節(jié)點(diǎn)
        {
            temp1=temp;
            head->next=NULL;
        }
        else 
        {
            temp1=temp->next;
            temp->next=NULL;
        }
    }
        head=sortList(head);//遞歸，此時不需要判斷是否為單節(jié)點(diǎn)鏈表，參考上方的返回條件，單節(jié)點(diǎn)鏈表會直接返回自身并且不進(jìn)行遞歸
        temp1=sortList(temp1);//遞歸


    return hebing(head,temp1);;
}