21xrx.com
2024-12-22 22:37:01 Sunday
登录
文章检索 我的文章 写文章
C++实现单链表排序
2023-07-06 21:36:38 深夜i     --     --
C++ 单链表 排序

单链表是一种常用的数据结构,它由一系列节点组成,每个节点包含一个数据元素和一个指向下一个节点的指针。在实际的编程中,我们需要对单链表进行排序,使其满足我们的需求。本文将介绍C++如何实现单链表排序。

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


struct ListNode {

  int val;

  ListNode *next;

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

};

接着,我们可以使用冒泡排序法对单链表进行排序。冒泡排序法的基本思想是遍历整个数组,比较相邻的两个元素,如果前一个元素比后一个元素大,则交换它们的位置,这样一轮下来,最大的元素就会被排到了最后。然后再重复这个过程,直到整个数组都被排好序。

对于单链表,我们可以使用类似的方法,但需要注意的是,我们不能直接交换节点的值,而是需要交换节点的指针。


ListNode* sortList(ListNode* head) {

  if (head == NULL || head->next == NULL) return head;

  ListNode *dummy = new ListNode(0);

  dummy->next = head;

  int len = 0;

  ListNode *p = head;

  while (p) {

    len++;

    p = p->next;

  }

  for (int i = 0; i < len; i++) {

    ListNode *cur = dummy->next, *pre = dummy;

    for (int j = 0; j < len - i - 1; j++) {

      if (cur->val > cur->next->val) {

        ListNode *tmp = cur->next;

        cur->next = cur->next->next;

        tmp->next = cur;

        pre->next = tmp;

        cur = tmp;

      }

      pre = pre->next;

      cur = cur->next;

    }

  }

  return dummy->next;

}

以上就是C++如何实现单链表排序的方法。虽然冒泡排序法的时间复杂度较高,为O(N^2),但在实际的编程中,它的实现简单易懂,适合小规模数据的排序。对于大规模数据的排序,我们可以选择更优秀的排序算法,如快速排序、归并排序等。

  
  
下一篇: C++继承与派生

评论区

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