LeetCode: 148. Sort List

题目描述

Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4

Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5

解题思路

该题快速排序， 归并排序都可以实现。这里用快速排序实现。

AC 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(head == nullptr || head->next == nullptr) return head;
        ListNode* anchorNode = head;
        ListNode *lowerNodeBeg = nullptr;
        ListNode *higherNodeBeg = nullptr;

        // partion 操作
        head = head->next;
        while(head != nullptr)
        {
            ListNode* curNode = head;
            head = head->next;

            if(anchorNode->val >= curNode->val)
            {
                curNode->next = lowerNodeBeg;
                lowerNodeBeg = curNode;
            }
            else
            {
                curNode->next = higherNodeBeg;
                higherNodeBeg = curNode;
            }
        }

        // 分别对左右边两边数据进行处理
        lowerNodeBeg = sortList(lowerNodeBeg);
        higherNodeBeg = sortList(higherNodeBeg);

        // 将大于 anchorNode 的数，anchorNode 的数 和 小于 anchorNode 的数连接起来
        ListNode *lowerNodeEnd = lowerNodeBeg;

        while(lowerNodeEnd != nullptr && lowerNodeEnd->next != nullptr)
        {
            lowerNodeEnd = lowerNodeEnd->next;
        }

        if(lowerNodeEnd == nullptr)
        {
            lowerNodeBeg = anchorNode;
        }
        else
        {
            lowerNodeEnd->next = anchorNode;
        }

        anchorNode->next = higherNodeBeg;

        return lowerNodeBeg;
    }
};