排序链表--字节跳动

少年的书桌上没有虚度的光阴

题目描述

请你对链表进行排序

思路分析

核心思想：归并排序

有三个部分

链表排序实现

1. `merge` 函数

21.见合并两个有序链表，

首先创建一个虚拟头节点 newhead，并使用指针 tail 来构建合并后的链表。
通过循环比较 list1 和 list2 节点的值，将较小值的节点连接到 tail 后面，并相应地移动指针。
当其中一个链表遍历完后，将另一个链表的剩余部分直接连接到 tail 后面。
最后返回虚拟头节点的下一个节点，即合并后链表的头节点。

2. `findMiddle` 函数

该函数用于寻找链表的中间节点，采用快慢指针的方法：

fast 指针每次移动两步，slow 指针每次移动一步。
当 fast 指针到达链表末尾时，slow 指针就指向链表的中间节点。

3. `sortList` 函数

这是核心的排序函数，使用归并排序算法对链表进行排序：

首先判断链表是否为空或只有一个节点，如果是则直接返回该链表。
调用 findMiddle 函数找到链表的中间节点，将链表分成左右两部分。
递归地对左右两部分链表分别调用 sortList 函数进行排序。
最后调用 merge 函数将两个有序的子链表合并成一个有序链表。

完整代码

class Solution {
public:
    // 合并两个有序链表
    ListNode* merge(ListNode* list1, ListNode* list2) {
        auto  newhead = new ListNode(0); // 使用明确的类型名称
        auto  tail = newhead;

        while (list1 && list2) {
            if (list1->val < list2->val) {
                tail->next = list1;
                list1 = list1->next;
            } else {
                tail->next = list2;
                list2 = list2->next;
            }
            tail = tail->next;
        }

        tail->next = list1 ? list1 : list2; // 处理剩余部分
        return newhead->next;
    }

    // 寻找中间节点
    ListNode* findMiddle(ListNode* head) {
        ListNode* fast = head;
        ListNode* slow = head;

        while (fast->next && fast->next->next) {
            fast = fast->next->next;
            slow = slow->next;
        }

        return slow;
    }

    // 归并排序链表
    ListNode* sortList(ListNode* head) {
        if (head==NULL ||head->next==NULL) 
                return head; // 检查链表长度

        // 找到链表的中间节点
        ListNode* mid = findMiddle(head);
        ListNode* right = mid->next;
        mid->next = nullptr; // 切分链表

        // 递归地对左右两部分进行排序
        ListNode* l = sortList(head);
        ListNode* r = sortList(right);

        // 合并两个有序链表
        return merge(l, r);
    }
}
};