题解 | 单链表的排序

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 the head node
 * @return ListNode类
 */
#include <stdio.h>
#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!=NULL && fast->next!=NULL){
        slow = slow->next;
        fast = fast->next->next;
    }

    struct ListNode* secondlyHead = slow->next;
    slow->next = NULL;

    struct ListNode* left = sortInList(head);
    struct ListNode* right = sortInList(secondlyHead);

    // 合并排序
    struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* tail = dummy;          // 借助这两个进行归并排序，头结点是虚拟的
    while (left!=NULL && right!=NULL) {     // 当一个链表遍历完成，直接将没有完成的直接接入后续结果
        if(left->val < right->val){
            tail->next = left;            // 将小的接入
            left = left->next;
        }else{
            tail->next = right;
            right = right->next;
        }
        tail = tail->next;
    } 
    // 将没有合并的直接接入后面
    if(left != NULL){
        tail->next = left;
    }
    if(right != NULL){
        tail->next = right;
    }

    return dummy->next;
    
}

方法：归并排序