数据结构：单链表的排序-德赢Vwin官网网

数据结构：单链表的排序

给定一个单链表的头结点head（该结点有值），长度为n的无序单链表，对其按升序排序后，返回新链表。如当输入链表 {3,1,4,5,2} 时，经升序排列后，原链表变为 {1,2,3,4,5}，对应的输出为 {1,2,3,4,5}。

代码实现

structListNode*sortInList(structListNode*head){
if(head==NULL)
returnNULL;
//添加一个头指针，指向head，方便后面的排序
structListNode*H;
H=malloc(sizeof(structListNode));
H->next=head;
//第一步：定义三个指针
structListNode*p,*q,*r;
//第二步：将p指向head，并将头指针断开链接
p=H->next;
H->next=NULL;
//遍历链表
while(p)
{
//第三步：q指向当前要操作的结点，p后移，r指向头指针
q=p;
p=p->next;
r=H;
//第四步：将r的后继数值与当前操作结点q的值进行比较
//若条件成立，r后移一个位置后，继续进行比较
//若条件不成立，跳出while循环，将q指向r的后继，r的后继指向q
while(r->next&&r->next->val< q->val)
r=r->next;
q->next=r->next;
r->next=q;
}
//第五步：返回头指针H的后继结点链表
returnH->next;
}

图解代码

第一步：定义三个指针

第二步：将p指向head，并将头指针断开链接

第三步：q指向当前要操作的结点，p后移，r指向头指针

第四步：将r的后继数值与当前操作结点q的值进行比较：若条件成立，r后移一个位置后，继续进行比较；若条件不成立，跳出while循环，将q指向r的后继，r的后继指向q

第五步：返回头指针H的后继结点链表

审核编辑：汤梓红

声明：本文内容及配图由入驻作者撰写或者入驻合作网站授权转载。文章观点仅代表作者本人，不代表德赢Vwin官网网立场。文章及其配图仅供工程师学习之用，如有内容侵权或者其他违规问题，请联系本站处理。举报投诉

C语言

C语言

+关注

关注
180

文章
7604

浏览量
136680
代码

代码

+关注

关注
30

文章
4779

浏览量
68518
数据结构

数据结构

+关注

关注
3

文章
573

浏览量
40121
单链表

单链表

+关注

关注
0

文章
13

浏览量
6918

原文标题：数据结构：单链表的排序

文章出处：【微信号：嵌入式攻城狮，微信公众号：嵌入式攻城狮】欢迎添加关注！文章转载请注明出处。

链表结点的数据结构该如何定义

当用户需要使用链表管理数据时，仅需关联数据和链表结点，最简单的方式是将数据和链表结点打包在一起。

发表于 09-20 16:28 •1.5w次阅读

<b class='flag-5'>链表</b>结点的<b class='flag-5'>数据结构</b>该如何定义

数据结构中最简单的链表

数据结构作为嵌入式工程师必修课程之一，今天，我们就来讲一讲数据结构中最简单的链表，包含链表的初始化、插入和遍历操作。链表在项目开发中使用的

发表于 06-13 17:40 •367次阅读

Linux Kernel数据结构:链表

Linux Kernel数据结构：链表原创 2016年10月20日 22:58:25标签：LINUX/kernel/链表 数据结构数据结构中

发表于 09-25 16:41

数据结构的几个重要知识点

线性结构、树形结构、图状结构，常用的数据结构有：数组、链表、堆栈、树、图等，常用的排序算法有：希

发表于 02-27 15:01

常见的数据结构

的，那样对于数据的使用简直是个悲剧。针对此类数据，数据结构提供了图存储结构，专门用于存储这类数据。二、数

发表于 05-10 07:58

数据结构链表的基本操作

嵌入式学习基础-数据结构链表的基本操作链表节点采用结构体的方式进行定义，下面是最基础的定义只有一个数据data，*pNext用于指向下一个节

发表于 12-22 08:05

C语言实现单链表举例

所谓链表，就是用一组任意的存储单元存储线性表元素的一种数据结构。链表又分为单链表、双向链表和循环

发表于 07-11 16:40 •87次下载

算法与数据结构——双向链表

第三章为算法与数据结构，本文为3.3 双向链表。

发表于 09-19 17:56 •7289次阅读

java数据结构学习

数据结构是对计算机内存中的数据的一种安排，数据结构包括数组，链表，栈，二叉树，哈希表等，算法则对对这些结构中的

发表于 11-29 09:46 •782次阅读

数据结构常见的八大排序算法

本文总结了数据结构常见的八大排序算法。详细分析请看下文

发表于 02-05 15:26 •1832次阅读

你知道Linux内核数据结构中双向链表的作用？

Linux 内核提供一套双向链表的实现，你可以在 include/linux/list.h 中找到。我们以双向链表着手开始介绍 Linux 内核中的数据结构 ，因为这个是在 Linux 内核中使用最为广泛的

发表于 05-14 17:27 •1875次阅读

什么是栈?数据结构中栈如何实现

今天放松一下，我们来看看数据结构中的栈，这节的知识点可以说是数据结构中最容易上手的知识点了，其实比起链表，其实链表也有栈和队列的模型，链表的

发表于 04-29 18:25 •0次下载

解析数据结构的常用七大排序算法

为了让大家掌握多种排序方法的基本思想，本篇文章带着大家对数据结构的常用七大算法进行分析：包括直接插入排序、希尔排序、冒泡排序、快速

发表于 03-16 08:22 •1673次阅读

Linux内核的链表数据结构

Linux内核实现了自己的链表数据结构，它的设计与传统的方式不同，非常巧妙也很通用。

发表于 03-24 11:34 •831次阅读

Linux内核中使用的数据结构

Linux内核代码中广泛使用了数据结构和算法，其中最常用的两个是链表和红黑树。链表 Linux内核代码大量使用了链表这种数据结构。

发表于 11-09 14:24 •485次阅读