学习在 C++ 中将合并排序算法与链表一起使用

一、引言

链表是一种常见的数据结构，用于存储一系列有序或无序的元素。在实际应用中，我们经常需要对链表进行排序。合并排序（Merge Sort）是一种高效的排序算法，具有稳定的排序性能和O(nlogn)的时间复杂度。本文将介绍如何在C++中将合并排序算法与链表一起使用，以便轻松实现链表的排序。

二、链表基础

链表是一种通过指针链接在一起的数据结构。每个节点包含数据和指向下一个节点的指针。在C++中，我们可以定义一个结构体来表示链表节点，如下所示：

struct ListNode {  

    int val;           // 节点值  

    ListNode* next;    // 指向下一个节点的指针  

    ListNode(int x) : val(x), next(nullptr) {} // 构造函数  

};

三、合并排序算法原理

合并排序算法采用分治策略，将待排序数组不断拆分为子数组，直到子数组长度为1或0，然后将子数组两两合并，直到最终得到有序数组。合并排序算法的时间复杂度为O(nlogn)，是一种稳定的排序算法。

四、合并排序与链表的结合

将合并排序算法应用于链表时，我们需要对链表进行拆分和合并操作。拆分操作可以通过找到链表的中间节点实现，合并操作则需要比较两个链表节点的值并进行链接。具体实现如下：

1.链表拆分

为了找到链表的中间节点，我们可以使用快慢指针法。定义两个指针slow和fast，初始时都指向链表的头节点。然后，slow每次移动一步，fast每次移动两步。当fast到达链表末尾时，slow刚好到达链表中间。代码如下：

ListNode* GetMiddleNode(ListNode* head) {    
    if (head == nullptr || head->next == nullptr) {  
        return head; // 对于空链表或只有一个节点的链表，返回头节点  
    }  
      
    ListNode* slow = head;    
    ListNode* fast = head;    
    while (fast != nullptr && fast->next != nullptr && fast->next->next != nullptr) {    
        slow = slow->next;    
        fast = fast->next->next;    
    }    
    return slow;    
}

2.链表合并

合并两个链表时，我们需要定义一个新的头节点dummy，用于连接合并后的链表。然后，比较两个链表的节点值，将较小的节点链接到新链表的末尾。重复此过程，直到其中一个链表为空。最后，将非空链表的剩余部分链接到新链表的末尾。代码如下：

ListNode* MergeLists(ListNode* list1, ListNode* list2) {  
    ListNode dummy(0);  
    ListNode* tail = &dummy;  
  
    while (list1 && list2) {  
        if (list1->val val) {  
            tail->next = list1;  
            list1 = list1->next;  
        } else {  
            tail->next = list2;  
            list2 = list2->next;  
        }  
        tail = tail->next;  
    }  
  
    tail->next = (list1 != nullptr) ? list1 : list2;  
    return dummy.next;  
}

3.合并排序链表实现

结合以上两个步骤，我们可以实现链表的合并排序。首先，递归地将链表拆分为子链表，直到子链表长度为1或0。然后，将子链表两两合并，直到最终得到有序链表。代码如下：

ListNode* MergeSortList(ListNode* head) {  
    if (head == nullptr || head->next == nullptr) {  
        return head; // 链表为空或只有一个节点，无需排序  
    }  
    ListNode* middle = GetMiddleNode(head); // 找到链表中间节点  
    ListNode* nextToMiddle = middle->next; // 记录中间节点的下一个节点  
    middle->next = nullptr; // 将链表拆分为两个子链表  
    return MergeLists(MergeSortList(head), MergeSortList(nextToMiddle)); // 递归地对子链表进行排序并合并结果  
}

五、性能分析

合并排序算法的时间复杂度为O(nlogn)，其中n为链表的长度。在空间复杂度方面，由于递归实现需要使用栈空间，因此空间复杂度为O(logn)。这使得合并排序算法在处理大规模数据时具有较高的效率。

六、应用示例

下面是一个简单的示例，展示如何使用合并排序算法对链表进行排序：

#include   

void PrintList(ListNode* head) {

    while (head != nullptr) {

        std::cout val next;

    }

    std::cout  2 -> 1 -> 3

    ListNode* head = new ListNode(4);

    head->next = new ListNode(2);

    head->next->next = new ListNode(1);

    head->next->next->next = new ListNode(3);  
    std::cout