排序链表

数据结构 算法

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/sort-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

给你链表的头结点 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 = []
输出：[]

提示：

链表中节点的数目在范围 [0, 5 * 10^4] 内
-10^5 <= Node.val <= 10^5

本人提交代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        // return mergeSort( head );
        // quickSort( head, NULL );
        // return head;
        return mergeSort( head );
    }

    ListNode* mergeSort( ListNode* head )
    {
        if ( !head || !head->next )
            return head;

        ListNode* pPrev = head;
        ListNode* pSlow = head;
        ListNode* pFast = head;
        while ( pFast && pFast->next )
        {
            pPrev = pSlow;
            pFast = pFast->next->next;
            pSlow = pSlow->next;
        }
        pPrev->next = NULL;

        return mergeSortedList( mergeSort(head), mergeSort(pSlow) );
    }

    void quickSort( ListNode* head, ListNode* end )
    {
        if ( head == NULL || head == end )
            return;
        
        ListNode* pNode = head->next;
        ListNode* pSlow = head;
        while ( pNode != end )
        {
            if ( pNode->val < head->val )
            {
                pSlow = pSlow->next;
                swap( pNode->val, pSlow->val );
            }
            pNode = pNode->next;
        }
        swap ( pSlow->val, head->val );
        quickSort( head, pSlow );
        quickSort( pSlow->next, end );
    }

private:
    ListNode* mergeSortedList( ListNode* l1, ListNode* l2 )
    {
        if ( !l1 )
            return l2;
        if ( !l2 )
            return l1;

        ListNode* pHead = NULL;
        if ( l1->val < l2->val )
        {
            pHead = l1;
            l1->next = mergeSortedList( l1->next, l2 );
        }
        else
        {
            pHead = l2;
            l2->next = mergeSortedList( l1, l2->next );
        }
        return pHead;
    }
};

本文由 BeijingJW 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Jun 2, 2023 at 05:22 pm