21xrx.com
2024-11-08 23:30:52 Friday
登录
文章检索 我的文章 写文章
C++链表排序算法详解
2023-07-13 14:59:12 深夜i     --     --
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),是一种高效的排序算法。在实际应用中,我们可以根据需要选择不同的排序算法,以提高程序的运行效率。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复