题解 | NO.12#单链表的排序#3.6

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */

    ListNode* merge(ListNode *head1, ListNode *head2){
        //一个空了，直接返回另一个
        if(head1 == NULL)
            return head2;
        if(head2 == NULL)
            return head1;
        //两链表都不空
        ListNode *head = new ListNode(0);   //设置哨兵结点
        ListNode *temp = head;

        while(head1 && head2){
            if(head1->val <= head2->val){
                temp->next = head1;
                head1 = head1->next;
            }else{
                temp->next = head2;
                head2 = head2->next;
            }
            //指针后移
            temp = temp->next;
        }
        if(head1)
            temp->next = head1;
        if(head2)
            temp->next = head2;
        return head->next;
    }

    ListNode* sortInList(ListNode* head) {
        // 采用分而治之的思想，用归并排序
        if(head == NULL || head->next == NULL)   //忘了这一步，这是递归出口，非常重要
            return head;
        ListNode* left = head;
        ListNode* mid = head->next;
        ListNode* right = head->next->next;
        //用快慢指针找中点
        while(right != NULL && right->next != NULL){
            left = left->next;
            mid = mid->next;
            right = right->next->next;
        }
        //左边指针指向左段的最后一个结点，从这里后边断开
        left->next = NULL;
        //分成两段排序，合并排好序的两段
        return merge(sortInList(head),sortInList(mid));
    }
};