C++链表排序算法详解 |21xrx.com

C++链表排序算法详解

2023-07-13 14:59:12 深夜i 18 0

C++ 链表排序算法详解

C++ 链表排序算法是一个重要的排序算法，它将一个链表中的元素按照某种规则进行排序，使得链表中的所有元素都按照一定的顺序排列。C++ 链表排序算法是一个高效的排序算法，它可以在较短的时间内完成排序操作，适用于需要排序的元素较多的场合。

C++ 链表排序算法的实现方法有很多种，这里我们介绍一种常见的方法。

首先，我们需要定义一个链表节点的结构体，该结构体包含一个数据域和一个指针域，指向下一个节点。

struct ListNode
{
  int val;
  ListNode *next;
  ListNode(int x) : val(x), next(NULL) {}
};

接下来，我们可以使用递归的方式对链表进行排序。具体步骤如下：

1. 找到链表的中间节点，将链表分成左右两个子链表。

2. 对左右两个子链表分别进行排序。

3. 合并左右两个子链表，得到排序后的链表。

代码实现如下：

class Solution
{
public:
  ListNode* sortList(ListNode* head)
  {
    if (!head || !head->next)
      return head;
    // 找到中间节点
    ListNode *mid = findMiddle(head);
    ListNode *left = head;
    ListNode *right = mid->next;
    mid->next = NULL;
    // 分别对左右子链表递归排序
    left = sortList(left);
    right = sortList(right);
    // 合并左右子链表
    return merge(left, right);
  }
private:
  ListNode* findMiddle(ListNode* head)
  {
    ListNode *slow = head;
    ListNode *fast = head->next;
    while (fast && fast->next)
    
      slow = slow->next;
      fast = fast->next->next;
    
    return slow;
  }
  ListNode* merge(ListNode* l1, ListNode* l2)
  {
    ListNode *dummy = new ListNode(0);
    ListNode *cur = dummy;
    while (l1 && l2)
    {
      if (l1->val < l2->val)
      
        cur->next = l1;
        l1 = l1->next;
      
      else
      
        cur->next = l2;
        l2 = l2->next;
      
      cur = cur->next;
    }
    if (l1) cur->next = l1;
    if (l2) cur->next = l2;
    return dummy->next;
  }
};

通过以上代码实现，我们在 C++ 中成功完成了链表排序算法。该算法的时间复杂度为 O(nlogn)，是一种高效的排序算法。在实际应用中，我们可以根据需要选择不同的排序算法，以提高程序的运行效率。

上一篇: idea打包java可执行jar包

下一篇: C++中可以使用嵌套类吗？

评论区

相似文章