当前位置：首页 > news >正文

Leetcode—148. 排序链表【中等】

news 2025/6/23 5:06:37

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;}
};