单链表的排序（C++）

单链表的排序（C++）

引用

CSDN

1.

https://blog.csdn.net/m0_74091276/article/details/145839780

问题描述

给定一个节点数为n的无序单链表，需要将其按升序排序。数据范围：0 < n ≤ 100000，保证节点权值在[-109, 109]之内。要求空间复杂度为O(n)，时间复杂度为O(nlogn)。

示例1

输入：

[1,3,2,4,5]

返回值：

{1,2,3,4,5}

示例2

输入：

[-1,0,-2]

返回值：

{-2,-1,0}

解题思路

本题采用归并排序算法对单链表进行排序。具体步骤如下：

1. Merge函数：用于合并两个已排序的链表。通过逐个节点比较的方式，将较小的节点接到结果链表中，最终返回合并后的链表头。

2. sortInList函数：通过快慢指针将链表拆分为两部分，递归地对每部分进行排序。具体来说，慢指针left指向链表的头节点，快指针right和mid用于找到链表的中点，将链表分成两半，然后对每半部分递归排序，最后通过Merge函数合并两个有序链表。

代码实现

ListNode* Merge(ListNode* head1, ListNode* head2)
{
    if(head1 == nullptr) return head2;
    if(head2 == nullptr) return head1;
    auto ret = new ListNode(-1);
    auto head = ret;
    while (head1 && head2) {
        if (head1->val < head2->val) {
            ret->next = head1;
            head1 = head1->next;
        }
        else {
            ret->next = head2;
            head2 = head2->next;
        }
        ret = ret->next;
    }
    if (head1) {
        ret->next = head1;
    }
    if (head2) {
        ret->next = head2;
    }
    return head->next;
} 

ListNode* sortInList(ListNode* head) {
    if (head == nullptr || head->next == nullptr)
    {
        return head;
    }
    ListNode* left = head, *mid = head->next, *right = head->next;
    while (right && right->next) {
        left = left->next;
        mid = mid->next;
        right = right->next->next;
    }
    left->next = nullptr;
    return Merge(sortInList(head), sortInList(mid));
}  

代码解析

1. 归并排序

   如果链表为空或只有一个节点，直接返回链表；通过快慢指针将链表拆分成两部分，递归地对每部分进行排序，然后使用Merge函数合并排序后的子链表，最终返回排序后的链表。

   ListNode* sortInList(ListNode* head) {
       if (head == nullptr || head->next == nullptr)
       {
           return head;
       }
       ListNode* left = head, *mid = head->next, *right = head->next;
       while (right && right->next) {
           left = left->next;
           mid = mid->next;
           right = right->next->next;
       }
       left->next = nullptr;
       return Merge(sortInList(head), sortInList(mid));
   }  
   

2. 合并两个已排序的链表

   如果其中一个链表为空，直接返回另一个链表；否则，创建虚拟头节点ret，逐个比较两个链表的节点，将较小的节点连接到结果链表。最后将剩余的部分连接到结果链表，返回合并后的链表。

   ListNode* Merge(ListNode* head1, ListNode* head2)
   {
       if(head1 == nullptr) return head2;
       if(head2 == nullptr) return head1;
       auto ret = new ListNode(-1);
       auto head = ret;
       while (head1 && head2) {
           if (head1->val < head2->val) {
               ret->next = head1;
               head1 = head1->next;
           }
           else {
               ret->next = head2;
               head2 = head2->next;
           }
           ret = ret->next;
       }
       if (head1) {
           ret->next = head1;
       }
       if (head2) {
           ret->next = head2;
       }
       return head->next;
   }   
   

总结

本文介绍了如何使用归并排序对链表进行排序。首先通过Merge函数合并两个有序链表，再通过sortInList函数递归地拆分链表并排序。归并排序的优势在于其稳定性和O(nlogn)的时间复杂度，尤其适合链表结构的排序，因为它不需要额外的数组空间。通过快慢指针的拆分和递归合并，最终实现了一个高效的链表排序算法。