Leetcode-148.排序链表 [medium

最编程 2024-10-06 07:08:08

...

2024每日刷题（171）

Leetcode—148. 排序链表

在这里插入图片描述

C++实现代码

/**
 * 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) {
        ListNode dummy(0, head);
        int len = getLen(head);
        for(int k = 1; k < len; k *= 2) {
            ListNode* cur = dummy.next;
            ListNode* tail = &dummy;
            while(cur) {
                ListNode* l = cur;
                ListNode* r = split(l, k);
                cur = split(r, k);
                auto[mergeHead, mergeTail] = merge(l, r);
                tail->next = mergeHead;
                tail = mergeTail;
            }
        }
        return dummy.next;
    }
private:
    int getLen(ListNode* head) {
        ListNode* cur = head;
        int len = 0;
        while(cur) {
            len++;
            cur = cur->next;
        }
        return len;
    }

    pair<ListNode*, ListNode*> merge(ListNode* l, ListNode* r) {
        ListNode dummy(0);
        ListNode* tail = &dummy;
        while(l && r) {
            if(l->val > r->val) {
                swap(l, r);
            }
            tail->next = l;
            l = l->next;
            tail = tail->next;
        }
        tail->next = l? l: r;
        while(tail->next) {
            tail = tail->next;
        }
        return {dummy.next, tail};
    }

    ListNode* split(ListNode* head, int k) {
        while(--k && head) {
            head = head->next;
        }
        ListNode* rest = head ? head->next: nullptr;
        if(head != nullptr) {
            head->next = nullptr;
        }
        return rest;
    }
};