LV070-单链表进阶操作
一、单链表反转
1. 头插法
头插法反转链表，是指在原有链表的基础上，依次将位于原链表头部的节点取出来，然后采用从头部插入的方式生成一个新链表，则新生成的链表即为原链表的反转链表啦。
1.1 头插法实现步骤
1.2 函数实现
c
/**
* @Function : slinkedlist_reverse_insertH
* @brief : 头插法反转单链表
* @param H : _slinkedlink 类型，表示要反转的单链表的地址
* @return : int 类型， 链表不存在则返回-1; 反转完成返回 0
* @Description:
*/
int slinkedlist_reverse_insertH(_slinkedlink H)
{
/* 定义两个单链表结构体指针变量 */
_slinkedlink p;
_slinkedlink q;
/* 1. 判断单链表是否存在 */
if (H == NULL)
{
printf("[WARN ]Single linked list is not existed!\n");
return -1;
}
/* 2. 判断链表仅有头节点或者只有两个节点 */
if (H->next == NULL || H->next->next == NULL)
{
return 0;
}
/* 3. 拆分链表为两部分 */
p = H->next->next;
H->next->next = NULL;
/* 4. 开始反转 */
while (p != NULL)
{
q = p;
p = p->next;
q->next = H->next;
H->next = q;
}
return 0;
}2. 迭代法
迭代法反转就是从当前链表的首元节点开始，一直遍历至链表的最后一个节点，这期间会逐个改变所遍历到的节点的指针域，令其指向前一个节点，最后再令原始的头节点指向反转后的第一个节点。
2.1 迭代法实现步骤
2.2 函数实现
c
/**
* @Function : slinkedlist_reverse_iteration
* @brief : 迭代法反转链表
* @param H : _slinkedlink 类型，表示要反转的单链表的地址
* @return : _slinkedlink 类型，反转成功则返回反转后的链表地址; 反转失败则返回 NULL
* @Description: 需要处理头节点，在函数内已经处理。
*/
_slinkedlink slinkedlist_reverse_iteration(_slinkedlink H)
{
/* 定义三个单链表结构体指针变量 */
_slinkedlink p1;
_slinkedlink p2;
_slinkedlink p3;
/* 1. 判断单链表是否存在 */
if (H == NULL)
{
printf("Single linked list is not existed!\n");
return NULL;
}
/* 2. 判断是否为空表 */
if (H->next == NULL)
{
printf("Single linked list H is empty!\n");
return H;
}
/* 3. 开始反转操作, */
p1 = NULL;
/* 跳过链表头，H 会一直指向链表头 */
p2 = H->next;
p3 = H->next->next;
while (p2 != NULL)
{
/* 反转后一个节点指向前一个节点 */
p2->next = p1;
/* 三个指针向后移动一个节点 */
p1 = p2;
p2 = p3;
/* p3 会先到 NULL, 此时 p3 已经不可以再进行 p3 = p3-> next; 操作了，此时的 p2 是位于最后一个节点，即 p2-> next = NULL*/
if (p3 != NULL)
p3 = p3->next;
}
/* 4.加上原来的头节点 */
/* 反转完成后，p1 指向原先的随后一个节点, p2 和 p3 指向 NULL, 反转链表的最后一个节点是原来的头节点 */
H->next = p1;
return H;
}3. 递归法
和迭代反转法的思想恰好相反，递归反转法的实现是从链表的尾节点开始，依次向前遍历，遍历过程依次改变各节点的指向，即令其指向前一个节点。
3.1 递归法实现步骤
递归法有些复杂了，用 ppt 做的动图不怎么反应的出来，所以这里就省略了，简单通过代码理解吧。（个人觉得涉及到递归的，似乎都不怎么好理解）。
3.2 函数实现
c
/**
* @Function : slinkedlist_reverse_recursiveH
* @brief : 递归法反转单链表
* @param H : _slinkedlink 类型，表示要反转的单链表的地址
* @return : _slinkedlink 类型，反转成功则返回反转后的链表地址; 反转失败则返回 NULL
* @Description: 处理递归反转时的头节点问题。
*/
_slinkedlink slinkedlist_reverse_recursiveH(_slinkedlink H)
{
/* 定义一个单链表结构体指针变量 */
_slinkedlink p1;
/* 1. 判断单链表是否存在 */
if (H == NULL)
{
printf("Single linked list is not existed!\n");
return NULL;
}
/* 2. 去掉头节点 */
p1 = H->next;
/* 3.去掉头节点的部分进行反转 */
p1 = slinkedlist_reverse_recursive(p1);
/* 4.头节点指向反转后的无节点链表 */
H->next = p1;
return H;
}
/**
* @Function : slinkedlist_reverse_recursive
* @brief : 递归法反转单链表递归实现
* @param H : _slinkedlink 类型，表示要反转的单链表的地址
* @return : _slinkedlink 类型，反转成功则返回反转后的链表地址; 反转失败则返回 NULL
* @Description:
* @Attention : 原来的尾节点会成为头节点，头节点会成为尾节点，递归函数内无法处理，重新定义一个函数进行处理。
*/
_slinkedlink slinkedlist_reverse_recursive(_slinkedlink H)
{
/* 定义一个单链表结构体指针变量 */
_slinkedlink p1;
/* 1. 判断单链表是否存在 */
if (H == NULL)
{
printf("Single linked list is not existed!\n");
return NULL;
}
/* 2. 递归结束的条件 */
if (H->next == NULL)
{
return H;
}
/* 3. 开始反转操作, */
p1 = slinkedlist_reverse_recursive(H->next);
H->next->next = H;
H->next = NULL;
return p1;
}4. 本地逆置法
本地逆置法和头插法的实现思想类似，唯一的区别在于，头插法是通过建立一个新链表实现的，而就地逆置法则是直接对原链表做修改，从而实现将原链表反转。
4.1 本地逆置法实现步骤
4.2 函数实现
c
/**
* @Function : slinkedlist_reverse_local
* @brief : 本地逆置法反转单链表
* @param H : _slinkedlink 类型，表示要反转的单链表的地址
* @return : _slinkedlink 类型，反转成功则返回反转后的链表地址; 反转失败则返回 NULL
* @Description:
* @Attention : 需要处理头节点, 函数内已处理。
*/
_slinkedlink slinkedlist_reverse_local(_slinkedlink H)
{
/* 定义两个单链表结构体指针变量 */
_slinkedlink p;
_slinkedlink q;
/* 1. 判断单链表是否存在 */
if (H == NULL)
{
printf("Single linked list is not existed!\n");
return NULL;
}
/* 2. 判断链表仅有头节点或者只有两个节点 */
if (H->next == NULL || H->next->next == NULL)
{
return H;
}
/* 3. 开始反转操作 */
p = H->next;
q = H->next->next;
while (q != NULL)
{
p->next = q->next;
q->next = H->next;
H->next = q;
q = p->next;
}
return H;
}二、单链表排序
1. 排序方法
这里使用冒泡法实现链表的排序。
2. 函数实现
c
/**
* @Function : slinkedlist_bubble_sort
* @brief : 单链表排序（冒泡法排序）
* @param H : _slinkedlink 类型，表示要排序的单链表的地址
* @param mode ：int 类型，排序模式 0, 降序; 1, 升序
* @return : _slinkedlink 类型，排序完成则返回反转后的链表地址; 否则则返回 NULL
* @Description:
*/
_slinkedlink slinkedlist_bubble_sort(_slinkedlink H, int mode)
{
/* 定义三个链表结构体指针变量 */
_slinkedlink p, q, temp;
int i, j;
int len = 0;
/* 1.判断链表是否为存在, 不存在则直接返回 */
if (H == NULL)
{
printf("H is NULL(not exist)!\n");
return NULL;
}
/* 2.求链表长度 */
len = slinkedlist_length(H);
/* 3.冒泡排序 */
for(i = 0; i < len-1; i++)/* 外层循环, 进行 len-1 趟数据比较 */
{
/* 进行完一轮后，从头开始进行下一轮 */
q = H->next;/* 令 q 指向第一个结点 */
p = q->next;/* 令 p 指向后一个结点 */
temp = H; /* 让 temp 始终指向 q 前一个结点，方便交换 */
for(j = 0; j < len-1-i; j++) /* 每一趟进行 len-1-i 次比较 */
{
if(mode == 1 && (q->data > p->data))/* 如果该结点的值大于后一个结点，则交换*/
{
q->next = p->next;
p->next = q;
temp->next = p;
}
else if(mode == 0 && (q->data < p->data))/* 如果该结点的值小于后一个结点，则交换*/
{
q->next = p->next;
p->next = q;
temp->next = p;
}
/* 移动到下一个节点 */
temp = temp->next;
q = temp->next;
p = q->next;
}
}
return H;
}三、链表相交判定
1. 判定方法
链表相交？既然链表之间的节点是指针联系起来的，那么他们就完全有可能会有共同的部分，只考虑相交的话，可能的情况有以下三种：
但是根据单链表中每个节点的指针只能指向一个地址，所以情况 2 和情况 3 是不可能存在的。既然是只有情况 1 ，那么这也就意味着它们的尾节点地址必然是相同的，都遍历到结尾，比较尾节点就可以知道他们是否相交啦。
2. 函数实现
c
/**
* @Function : slinkedlist_intersect
* @brief : 判断两链表是否相交
* @param H1 : _slinkedlink 类型，链表 H1 的首地址
* @param H2 : _slinkedlink 类型，链表 H2 的首地址
* @return : int 类型，1, 两个链表相交; 0, 两个链表不相交;-1, 链表不存在
* @Description:
*/
int slinkedlist_intersect(_slinkedlink H1, _slinkedlink H2)
{
/* 定义两个个链表结构体指针变量 */
_slinkedlink p;
_slinkedlink q;
/* 1. 判断链表是否为存在, 不存在则直接返回 */
if (H1 == NULL || H2 == NULL)
{
printf("Single linked list H1 or H2 is not existed!\n");
return -1;
}
/* 2. 寻找尾节点 */
p = H1;
q = H2;
while (p->next)
{
p = p->next;
}
while (q->next)
{
q = q->next;
}
/* 3. 判断是否相交 */
if (p == q)
return 1;
else
return 0;
}四、相邻节点和最大
1. 实现思路
问题：设节点 data 域为整型，求链表中相邻两结点 data 值之和为最大的第一结点的指针。
思路：设 p ， q 分别为链表中相邻两节点指针，求 p-> data+q-> data 为最大的那一组值，返回其相应的指针 p 。
2. 函数实现
c
/**
* @Function : slinkedlist_adjmax
* @brief : 求相邻两节点和最大时的第一个节点指针
* @param H : _slinkedlink 类型，链表 H 的首地址
* @param value：data_t * 类型，存放相邻两节点和的最大值，需要传入地址
* @return : _slinkedlink 类型，链表不存在返回 NULL; 否则返回相邻两节点和最大时的第一个节点指针
* @Description:
*/
_slinkedlink slinkedlist_adjmax(_slinkedlink H, data_t *value)
{
/* 定义单个结构体变量指针, r 用于记录此次比较的目标节点 */
_slinkedlink p, q, r;
data_t sum;
/* 1.判断链表是否为存在, 不存在则直接返回 */
if (H == NULL)
{
printf("H is NULL(not exist)!\n");
return NULL;
}
/* 2. 判断是否至少有三个节点，若小于三个节点，则直接返回 H 即可 */
if (H->next == NULL || H->next->next == NULL || H->next->next->next == NULL)
{
return H;
}
/* 3. 开始比较相邻两节点和的值，找出最大值 */
q = H->next;
p = H->next->next; /* p = q-> next; */
r = q;
sum = q->data + p->data;
while (p->next != NULL)
{
p = p->next;
q = q->next;
if (sum < q->data + p->data)
{
sum = q->data + p->data;
r = q;
}
}
/* 4. 传回最大值 */
*value = sum;
return r;
}五、完整程序
1. slinkedlist.c
c
/** ==== ==== ==== ==== ==== ==== ==== ==== ==== ==== ==== ==== ==== =
* Copyright © hk. 2022-2025. All rights reserved.
* File name : slinkedlist.c
* Author : qidaink
* Date : 2022-10-21
* Version :
* Description:
* Others :
* Log :
* ==== ==== ==== ==== ==== ==== ==== ==== ==== ==== ==== ==== ==== ==
*/
#include <stdio.h>
#include <stdlib.h>
#include "slinkedlist.h"
/**
* @Function : slinkedlist_create
* @brief : 单链表创建
* @param arg : none
* @return : _slinkedlink 类型，NULL, 内存申请失败; H, 单链表地址
* @Description: 其实就是创建一个节点
*/
_slinkedlink slinkedlist_create(void)
{
/* 1.定义一个单链表结构体指针变量 */
_slinkedlink H;
/* 2.申请内存空间 */
H = (_slinkedlink)malloc(sizeof(_slinkednode));
/* 3.判断是否申请成功 */
if (H == NULL)
{
printf("[ERROR]Single linked list malloc failed!\n");
return H;
}
/* 4.初始化内存空间 */
H->data = 0;
H->next = NULL;
return H;
}
/**
* @Function : slinkedlist_free
* @brief : 单链表空间释放（释放整个单链表占用的内存空间）
* @param H : _slinkedlink 类型，表示要释放的单链表的地址
* @return : _slinkedlink 类型，NULL, 表示释放完成
* @Description:
*/
_slinkedlink slinkedlist_free(_slinkedlink H)
{
/* 定义一个单链表结构体指针变量 */
_slinkedlink p;
/* 1. 判断单链表是否存在 */
if (H == NULL)
{
printf("[WARN ]Single linked list is not existed!\n");
return NULL;
}
/* 2. 开始释放内存 */
p = H;
printf("Single linked list free:");
while (H != NULL)
{
p = H;
printf("%d ", p->data);
/* p 和 H 指向同一个地址空间，要先移动 H， 再释放，否则后边的节点地址就丢掉了 */
H = H->next;
free(p);
}
puts(""); /* 自带换行 */
return NULL;
}
/**
* @Function : slinkedlist_show
* @brief : 单链表数据显示
* @param H : _slinkedlink 类型，表示要释放的单链表的地址
* @return : int 类型，0, 显示成功;-1, 单链表不存在
* @Description:
*/
int slinkedlist_show(_slinkedlink H)
{
/* 定义一个单链表结构体指针变量 */
_slinkedlink p;
/* 1. 判断单链表是否存在 */
if (H == NULL)
{
printf("[WARN ]Single linked list is not existed!\n");
return -1;
}
/* 2. 遍历所有节点 */
p = H;
printf("Single linked list:");
while (p->next != NULL)
{
printf("%d ", p->next->data);
p = p->next;
}
puts(""); /* 自带换行 */
return 0;
}
/**
* @Function : slinkedlist_node_get
* @brief : 单链表节点查找（按位置查找）
* @param H : _slinkedlink 类型，表示要查找的单链表的地址
* @param pos : int 类型，表示要查找的节点位置，pos 大于等于 -1
* @return : _slinkedlink 类型，查找成功则返回查找到的节点的地址，否则返回 NULL
* @Description:
*/
_slinkedlink slinkedlist_node_get(_slinkedlink H, int pos)
{
/* 定一个单链表结构体指针变量 */
_slinkedlink p;
int i = 0;
/* 1. 判断单链表是否存在 */
if (H == NULL)
{
printf("[WARN ]Single linked list is not existed!\n");
return NULL;
}
/* 2. 检查参数是否合法 */
if (pos == -1) /* pos = -1 表示查找的是头节点 */
{
return H;
}
/* 这里可以防止参数非法，而返回 H 的情况，可以防止删除节点函数误删 */
if (pos < -1)
{
printf("[ERROR]get pos is invalid\n");
return NULL;
}
/* 3. 开始遍历节点，查找所需节点 */
p = H;
i = -1; /* 一共需要循环 pos + 1 次 */
while (i < pos)
{
p = p->next;
if (p == NULL) /* 已经遍历到单链表尾部了 */
{
printf("[ERROR]get pos is invalid\n");
return NULL;
}
i++;
}
return p;
}
/**
* @Function : slinkedlist_tail_insert
* @brief : 单链表尾部插入数据
* @param H : _slinkedlink 类型，表示要插入节点的单链表的地址
* @param value: data_t 类型，表示要插入的数据
* @return : int 类型，0, 插入成功;-1, 插入失败
* @Description:
*/
int slinkedlist_tail_insert(_slinkedlink H, data_t value)
{
/* 定义两个个单链表结构体指针变量 */
_slinkedlink p;
_slinkedlink q;
/* 1. 判断单链表是否存在 */
if (H == NULL)
{
printf("[WARN ]Single linked list is not existed!\n");
return -1;
}
/* 2. 创建新节点并初始化 */
if ((p = (_slinkedlink)malloc(sizeof(_slinkednode))) == NULL)
{
printf("[ERROR]The new node malloc failed!\n");
return -1;
}
p->data = value;
p->next = NULL;
/* 3. 寻找尾节点 */
q = H;
while (q->next != NULL)
{
q = q->next;
}
/* 3. 插入新节点 */
q->next = p;
return 0;
}
/**
* @Function : slinkedlist_insert
* @brief : 单链表在指定位置插入节点
* @param H : _slinkedlink 类型，表示要插入节点的单链表的地址
* @param value: data_t 类型，彪悍死要插入的数据
* @param pos : int 类型，表示要插入的节点位置，pos 大于等于 0
* @return : int 类型，0, 插入成功;-1, 插入失败
* @Description:
*/
int slinkedlist_insert(_slinkedlink H, data_t value, int pos)
{
/* 定义两个单链表结构体指针变量 */
_slinkedlink p;
_slinkedlink q;
/* 1. 判断单链表是否存在 */
if (H == NULL)
{
printf("[WARN ]Single linked list is not existed!\n");
return -1;
}
/* 2. 获取插入位置的前一个节点 */
p = slinkedlist_node_get(H, pos - 1);
if (p == NULL)
{
printf("[WARN ]pos-1 = %d position is not existed!\n", pos - 1);
return -1;
}
/* 3. 创建新节点并初始化 */
if ((q = (_slinkedlink)malloc(sizeof(_slinkednode))) == NULL)
{
printf("[ERROR]The new node malloc failed\n");
return -1;
}
q->data = value;
q->next = NULL;
/* 4. 插入新节点 */
q->next = p->next;
p->next = q;
return 0;
}
/**
* @Function : slinkedlist_delete
* @brief : 删除指定位置节点
* @param H : _slinkedlink 类型，表示要删除节点的单链表的地址
* @param pos : int 类型，要删除的节点位置（pos 大于等于 0）
* @return : int 类型，0, 删除成功;-1, 删除失败
* @Description:
*/
int slinkedlist_delete(_slinkedlink H, int pos)
{
/* 定义两个单链表结构体指针变量 */
_slinkedlink p;
_slinkedlink q;
/* 1. 判断单链表是否存在 */
if (H == NULL)
{
printf("[WARN ]Single linked list is not existed!\n");
return -1;
}
/* 2. 获取删除位置的前一个节点 */
/* 注意在这里，不合法的 pos 范围会在获取节点函数中被处理 */
p = slinkedlist_node_get(H, pos - 1);
if (p == NULL)
{
printf("[WARN ]pos-1 = %d position is not existed!\n", pos - 1);
return -1;
}
if (p->next == NULL)
{
printf("delete pos is invalid!pos-1 = %d position is the last node!\n", pos - 1);
return -1;
}
/* 3. 更新节点 */
q = p->next;
p->next = q->next; /* p-> next = p-> next-> next; */
/* 4.释放删除的节点 */
printf("Single linked list node free:%d\n", q->data);
free(q);
q = NULL;
return 0;
}
/**
* @Function : slinkedlist_node_update
* @brief : 更新指定位置的节点数据
* @param H : _slinkedlink 类型，表示要更新数据的单链表的地址
* @param value: data_t 类型，表示要更新的数据
* @param pos : int 类型，要更新的节点位置（pos 大于等于 0）
* @return : int 类型， 0, 更新成功;-1, 更新失败
* @Description:
*/
int slinkedlist_node_update(_slinkedlink H, data_t value, int pos)
{
/* 定义一个单链表结构体指针变量 */
_slinkedlink p;
/* 1. 判断单链表是否存在 */
if (H == NULL)
{
printf("Single linked list is not existed!\n");
return -1;
}
if (pos < 0)
{
printf("update pos is invalid!\n");
return -1;
}
/* 2. 获取更新节点位置 */
p = slinkedlist_node_get(H, pos);
if (p == NULL)
{
printf("pos position is not existed!\n");
return -1;
}
/* 3. 更新节点 */
p->data = value;
return 0;
}
/**
* @Function : slinkedlist_length
* @brief : 获取单链表长度（不包含头节点）
* @param H : _slinkedlink 类型，表示要获取长度的单链表的地址
* @return : int 类型， 链表不存在则返回-1; 否则返回单链表长度
* @Description:
*/
int slinkedlist_length(_slinkedlink H)
{
/* 定义一个链表结构体指针变量 */
_slinkedlink p;
int len = 0;
/* 1.判断链表是否为存在, 不存在则直接返回 */
if (H == NULL)
{
printf("[WARN ]Single linked list is not existed!\n");
return -1;
}
/* 2.遍历链表 */
p = H;
while (p->next != NULL)
{
len++;
p = p->next;
}
return (len);
}
/**
* @Function : slinkedlist_reverse_insertH
* @brief : 头插法反转单链表
* @param H : _slinkedlink 类型，表示要反转的单链表的地址
* @return : int 类型， 链表不存在则返回-1; 反转完成返回 0
* @Description:
*/
int slinkedlist_reverse_insertH(_slinkedlink H)
{
/* 定义两个单链表结构体指针变量 */
_slinkedlink p;
_slinkedlink q;
/* 1. 判断单链表是否存在 */
if (H == NULL)
{
printf("[WARN ]Single linked list is not existed!\n");
return -1;
}
/* 2. 判断链表仅有头节点或者只有两个节点 */
if (H->next == NULL || H->next->next == NULL)
{
return 0;
}
/* 3. 拆分链表为两部分 */
p = H->next->next;
H->next->next = NULL;
/* 4. 开始反转 */
while (p != NULL)
{
q = p;
p = p->next;
q->next = H->next;
H->next = q;
}
return 0;
}
/**
* @Function : slinkedlist_reverse_iteration
* @brief : 迭代法反转链表
* @param H : _slinkedlink 类型，表示要反转的单链表的地址
* @return : _slinkedlink 类型，反转成功则返回反转后的链表地址; 反转失败则返回 NULL
* @Description: 需要处理头节点，在函数内已经处理。
*/
_slinkedlink slinkedlist_reverse_iteration(_slinkedlink H)
{
/* 定义三个单链表结构体指针变量 */
_slinkedlink p1;
_slinkedlink p2;
_slinkedlink p3;
/* 1. 判断单链表是否存在 */
if (H == NULL)
{
printf("Single linked list is not existed!\n");
return NULL;
}
/* 2. 判断是否为空表 */
if (H->next == NULL)
{
printf("Single linked list H is empty!\n");
return H;
}
/* 3. 开始反转操作, */
p1 = NULL;
/* 跳过链表头，H 会一直指向链表头 */
p2 = H->next;
p3 = H->next->next;
while (p2 != NULL)
{
/* 反转后一个节点指向前一个节点 */
p2->next = p1;
/* 三个指针向后移动一个节点 */
p1 = p2;
p2 = p3;
/* p3 会先到 NULL, 此时 p3 已经不可以再进行 p3 = p3-> next; 操作了，此时的 p2 是位于最后一个节点，即 p2-> next = NULL*/
if (p3 != NULL)
p3 = p3->next;
}
/* 4.加上原来的头节点 */
/* 反转完成后，p1 指向原先的随后一个节点, p2 和 p3 指向 NULL, 反转链表的最后一个节点是原来的头节点 */
H->next = p1;
return H;
}
/**
* @Function : slinkedlist_reverse_recursiveH
* @brief : 递归法反转单链表
* @param H : _slinkedlink 类型，表示要反转的单链表的地址
* @return : _slinkedlink 类型，反转成功则返回反转后的链表地址; 反转失败则返回 NULL
* @Description: 处理递归反转时的头节点问题。
*/
_slinkedlink slinkedlist_reverse_recursiveH(_slinkedlink H)
{
/* 定义一个单链表结构体指针变量 */
_slinkedlink p1;
/* 1. 判断单链表是否存在 */
if (H == NULL)
{
printf("Single linked list is not existed!\n");
return NULL;
}
/* 2. 去掉头节点 */
p1 = H->next;
/* 3.去掉头节点的部分进行反转 */
p1 = slinkedlist_reverse_recursive(p1);
/* 4.头节点指向反转后的无节点链表 */
H->next = p1;
return H;
}
/**
* @Function : slinkedlist_reverse_recursive
* @brief : 递归法反转单链表递归实现
* @param H : _slinkedlink 类型，表示要反转的单链表的地址
* @return : _slinkedlink 类型，反转成功则返回反转后的链表地址; 反转失败则返回 NULL
* @Description:
* @Attention : 原来的尾节点会成为头节点，头节点会成为尾节点，递归函数内无法处理，重新定义一个函数进行处理。
*/
_slinkedlink slinkedlist_reverse_recursive(_slinkedlink H)
{
/* 定义一个单链表结构体指针变量 */
_slinkedlink p1;
/* 1. 判断单链表是否存在 */
if (H == NULL)
{
printf("Single linked list is not existed!\n");
return NULL;
}
/* 2. 递归结束的条件 */
if (H->next == NULL)
{
return H;
}
/* 3. 开始反转操作, */
p1 = slinkedlist_reverse_recursive(H->next);
H->next->next = H;
H->next = NULL;
return p1;
}
/**
* @Function : slinkedlist_reverse_local
* @brief : 本地逆置法反转单链表
* @param H : _slinkedlink 类型，表示要反转的单链表的地址
* @return : _slinkedlink 类型，反转成功则返回反转后的链表地址; 反转失败则返回 NULL
* @Description:
* @Attention : 需要处理头节点, 函数内已处理。
*/
_slinkedlink slinkedlist_reverse_local(_slinkedlink H)
{
/* 定义两个单链表结构体指针变量 */
_slinkedlink p;
_slinkedlink q;
/* 1. 判断单链表是否存在 */
if (H == NULL)
{
printf("Single linked list is not existed!\n");
return NULL;
}
/* 2. 判断链表仅有头节点或者只有两个节点 */
if (H->next == NULL || H->next->next == NULL)
{
return H;
}
/* 3. 开始反转操作 */
p = H->next;
q = H->next->next;
while (q != NULL)
{
p->next = q->next;
q->next = H->next;
H->next = q;
q = p->next;
}
return H;
}
/**
* @Function : slinkedlist_bubble_sort
* @brief : 单链表排序（冒泡法排序）
* @param H : _slinkedlink 类型，表示要排序的单链表的地址
* @param mode ：int 类型，排序模式 0, 降序; 1, 升序
* @return : _slinkedlink 类型，排序完成则返回反转后的链表地址; 否则则返回 NULL
* @Description:
*/
_slinkedlink slinkedlist_bubble_sort(_slinkedlink H, int mode)
{
/* 定义三个链表结构体指针变量 */
_slinkedlink p, q, temp;
int i, j;
int len = 0;
/* 1.判断链表是否为存在, 不存在则直接返回 */
if (H == NULL)
{
printf("H is NULL(not exist)!\n");
return NULL;
}
/* 2.求链表长度 */
len = slinkedlist_length(H);
/* 3.冒泡排序 */
for (i = 0; i < len - 1; i++) /* 外层循环, 进行 len-1 趟数据比较 */
{
/* 进行完一轮后，从头开始进行下一轮 */
q = H->next; /* 令 q 指向第一个结点 */
p = q->next; /* 令 p 指向后一个结点 */
temp = H; /* 让 temp 始终指向 q 前一个结点，方便交换 */
for (j = 0; j < len - 1 - i; j++) /* 每一趟进行 len-1-i 次比较 */
{
if (mode == 1 && (q->data > p->data)) /* 如果该结点的值大于后一个结点，则交换*/
{
q->next = p->next;
p->next = q;
temp->next = p;
}
else if (mode == 0 && (q->data < p->data)) /* 如果该结点的值小于后一个结点，则交换*/
{
q->next = p->next;
p->next = q;
temp->next = p;
}
/* 移动到下一个节点 */
temp = temp->next;
q = temp->next;
p = q->next;
}
}
return H;
}
/**
* @Function : slinkedlist_intersect
* @brief : 判断两链表是否相交
* @param H1 : _slinkedlink 类型，链表 H1 的首地址
* @param H2 : _slinkedlink 类型，链表 H2 的首地址
* @return : int 类型，1, 两个链表相交; 0, 两个链表不相交;-1, 链表不存在
* @Description:
*/
int slinkedlist_intersect(_slinkedlink H1, _slinkedlink H2)
{
/* 定义两个个链表结构体指针变量 */
_slinkedlink p;
_slinkedlink q;
/* 1. 判断链表是否为存在, 不存在则直接返回 */
if (H1 == NULL || H2 == NULL)
{
printf("Single linked list H1 or H2 is not existed!\n");
return -1;
}
/* 2. 寻找尾节点 */
p = H1;
q = H2;
while (p->next)
{
p = p->next;
}
while (q->next)
{
q = q->next;
}
/* 3. 判断是否相交 */
if (p == q)
return 1;
else
return 0;
}
/**
* @Function : slinkedlist_adjmax
* @brief : 求相邻两节点和最大时的第一个节点指针
* @param H : _slinkedlink 类型，链表 H 的首地址
* @param value：data_t * 类型，存放相邻两节点和的最大值，需要传入地址
* @return : _slinkedlink 类型，链表不存在返回 NULL; 否则返回相邻两节点和最大时的第一个节点指针
* @Description:
*/
_slinkedlink slinkedlist_adjmax(_slinkedlink H, data_t *value)
{
/* 定义单个结构体变量指针, r 用于记录此次比较的目标节点 */
_slinkedlink p, q, r;
data_t sum;
/* 1.判断链表是否为存在, 不存在则直接返回 */
if (H == NULL)
{
printf("H is NULL(not exist)!\n");
return NULL;
}
/* 2. 判断是否至少有三个节点，若小于三个节点，则直接返回 H 即可 */
if (H->next == NULL || H->next->next == NULL || H->next->next->next == NULL)
{
return H;
}
/* 3. 开始比较相邻两节点和的值，找出最大值 */
q = H->next;
p = H->next->next; /* p = q-> next; */
r = q;
sum = q->data + p->data;
while (p->next != NULL)
{
p = p->next;
q = q->next;
if (sum < q->data + p->data)
{
sum = q->data + p->data;
r = q;
}
}
/* 4. 传回最大值 */
*value = sum;
return r;
}
/* 测试函数实现 */
int test_slinkedlist_tail_insert()
{
_slinkedlink H;
int a[5] = {1, 3, 4, 5, 6};
int i = 0;
H = slinkedlist_create();
if (H == NULL)
return -1;
for (i = 0; i < 5; i++)
{
slinkedlist_tail_insert(H, a[i]);
}
slinkedlist_show(H);
printf("H=%p\n", H);
H = slinkedlist_free(H);
printf("H=%p\n", H);
return 0;
}
void test_slinkedlist_node_get()
{
_slinkedlink H;
_slinkedlink p;
int a[5] = {1, 3, 4, 5, 6};
int i = 0;
H = slinkedlist_create();
if (H == NULL)
return;
for (i = 0; i < 5; i++)
{
slinkedlist_tail_insert(H, a[i]);
}
slinkedlist_show(H);
for (i = -2; i < 7; i++)
{
p = slinkedlist_node_get(H, i);
if (p != NULL)
printf("i = %d,value=%d\n", i, p->data);
}
printf("H=%p\n", H);
H = slinkedlist_free(H);
printf("H=%p\n", H);
}
void test_slinkedlist_insert()
{
_slinkedlink H;
int a[5] = {1, 3, 4, 5, 6};
int i = 0;
H = slinkedlist_create();
if (H == NULL)
return;
slinkedlist_insert(H, a[0], 0);
for (i = 1; i < 5; i++)
{
slinkedlist_insert(H, a[i], 1);
}
slinkedlist_show(H);
slinkedlist_insert(H, 100, 2);
slinkedlist_insert(H, 200, 50);
slinkedlist_insert(H, 300, -9);
slinkedlist_show(H);
printf("H=%p\n", H);
H = slinkedlist_free(H);
printf("H=%p\n", H);
}
void test_slinkedlist_delete()
{
_slinkedlink H;
int a[5] = {1, 3, 4, 5, 6};
int i = 0;
H = slinkedlist_create();
if (H == NULL)
return;
for (i = 0; i < 5; i++)
{
slinkedlist_tail_insert(H, a[i]);
}
slinkedlist_show(H);
slinkedlist_delete(H, -4);
slinkedlist_delete(H, 50);
slinkedlist_delete(H, 2);
slinkedlist_delete(H, 3);
slinkedlist_delete(H, 3);
slinkedlist_show(H);
printf("H=%p\n", H);
H = slinkedlist_free(H);
printf("H=%p\n", H);
}
void test_slinkedlist_node_update()
{
_slinkedlink H;
int a[5] = {1, 3, 4, 5, 6};
int i = 0;
H = slinkedlist_create();
if (H == NULL)
return;
for (i = 0; i < 5; i++)
{
slinkedlist_tail_insert(H, a[i]);
}
slinkedlist_show(H);
slinkedlist_node_update(H, 100, 2);
slinkedlist_show(H);
slinkedlist_node_update(H, 100, 0);
slinkedlist_show(H);
slinkedlist_node_update(H, 100, 4);
slinkedlist_show(H);
slinkedlist_node_update(H, 100, 5);
slinkedlist_show(H);
slinkedlist_node_update(H, 100, -1);
slinkedlist_show(H);
printf("H=%p\n", H);
H = slinkedlist_free(H);
printf("H=%p\n", H);
}
void test_slinkedlist_length()
{
_slinkedlink H;
int a[6] = {1, 3, 7, 5, 6, 8};
int i = 0;
H = slinkedlist_create();
if (H == NULL)
return;
for (i = 0; i < 6; i++)
{
slinkedlist_tail_insert(H, a[i]);
}
slinkedlist_show(H);
printf("len=%d\n", slinkedlist_length(H));
printf("H=%p\n", H);
H = slinkedlist_free(H);
printf("H=%p\n", H);
}
void test_slinkedlist_reverse_iteration()
{
_slinkedlink H;
int a[6] = {1, 3, 4, 5, 6, 7};
int i = 0;
H = slinkedlist_create();
if (H == NULL)
return;
for (i = 0; i < 6; i++)
{
slinkedlist_tail_insert(H, a[i]);
}
slinkedlist_show(H);
printf("H=%p\n", H);
H = slinkedlist_reverse_iteration(H);
slinkedlist_show(H);
printf("H=%p\n", H);
H = slinkedlist_free(H);
printf("H=%p\n", H);
}
void test_slinkedlist_reverse_recursiveH()
{
_slinkedlink H;
int a[6] = {1, 3, 4, 5, 6, 7};
int i = 0;
H = slinkedlist_create();
if (H == NULL)
return;
for (i = 0; i < 6; i++)
{
slinkedlist_tail_insert(H, a[i]);
}
slinkedlist_show(H);
printf("H=%p\n", H);
H = slinkedlist_reverse_recursiveH(H);
slinkedlist_show(H);
printf("H=%p\n", H);
H = slinkedlist_free(H);
printf("H=%p\n", H);
}
void test_slinkedlist_reverse_insertH()
{
_slinkedlink H;
int a[6] = {1, 3, 4, 5, 6, 7};
int i = 0;
H = slinkedlist_create();
if (H == NULL)
return;
for (i = 0; i < 6; i++)
{
slinkedlist_tail_insert(H, a[i]);
}
slinkedlist_show(H);
printf("H=%p\n", H);
slinkedlist_reverse_insertH(H);
slinkedlist_show(H);
printf("H=%p\n", H);
H = slinkedlist_free(H);
printf("H=%p\n", H);
}
void test_slinkedlist_reverse_local()
{
_slinkedlink H;
int a[6] = {1, 3, 7, 5, 6, 8};
int i = 0;
H = slinkedlist_create();
if (H == NULL)
return;
for (i = 0; i < 6; i++)
{
slinkedlist_tail_insert(H, a[i]);
}
slinkedlist_show(H);
printf("H=%p\n", H);
H = slinkedlist_reverse_local(H);
slinkedlist_show(H);
printf("H=%p\n", H);
H = slinkedlist_free(H);
printf("H=%p\n", H);
}
void test_slinkedlist_bubble_sort()
{
_slinkedlink H;
int a[] = {1, 5, 3, 2, 9, 10, 7};
int i = 0;
H = slinkedlist_create();
if (H == NULL)
return;
for(i = 0; i < sizeof(a)/sizeof(int); i++)
{
slinkedlist_tail_insert(H, a[i]);
}
slinkedlist_show(H);
H = slinkedlist_bubble_sort(H, 1);
slinkedlist_show(H);
H = slinkedlist_bubble_sort(H, 0);
slinkedlist_show(H);
printf("H=%p\n", H);
H = slinkedlist_free(H);
printf("H=%p\n", H);
}
void test_slinkedlist_adjmax()
{
_slinkedlink H;
_slinkedlink r;
data_t sum;
int a[] = {1, 5, 3, 2, 9, 10, 7};
int i = 0;
H = slinkedlist_create();
if (H == NULL)
return;
for(i = 0; i < sizeof(a)/sizeof(int); i++)
{
slinkedlist_tail_insert(H, a[i]);
}
slinkedlist_show(H);
r = slinkedlist_adjmax(H, &sum);
if (r != NULL && r != H)
{
printf("data=%d, sum=%d\n", r->data, sum);
}
slinkedlist_show(H);
printf("H=%p\n", H);
H = slinkedlist_free(H);
printf("H=%p\n", H);
}
void test_slinkedlist_intersect()
{
_slinkedlink H1;
_slinkedlink H2;
_slinkedlink H3;
_slinkedlink p1;
_slinkedlink p2;
_slinkedlink temp;
int a[] = {1, 2, 3};
int b[] = {4, 5, 6, 7};
int c[] = {8, 9, 10, 11, 12};
int i = 0;
H1 = slinkedlist_create();
H2 = slinkedlist_create();
H3 = slinkedlist_create();
if (H1 == NULL || H2 == NULL || H3 == NULL)
return;
for(i = 0; i < sizeof(a)/sizeof(int); i++)
{
slinkedlist_tail_insert(H1, a[i]);
}
for(i = 0; i < sizeof(b)/sizeof(int); i++)
{
slinkedlist_tail_insert(H2, b[i]);
}
for(i = 0; i < sizeof(c)/sizeof(int); i++)
{
slinkedlist_tail_insert(H3, c[i]);
}
slinkedlist_show(H1);
slinkedlist_show(H2);
slinkedlist_show(H3);
p1 = slinkedlist_node_get(H1, 2);
p2 = slinkedlist_node_get(H2, 3);
temp = p1->next;/* 保护后边的节点 */
p1->next = p2;
printf("=========intersect1 test=========\n");
slinkedlist_show(H1);
slinkedlist_show(H2);
slinkedlist_show(H3);
printf("H1,H2:%d\n", slinkedlist_intersect(H1, H2));
printf("H1,H3:%d\n", slinkedlist_intersect(H1, H3));
printf("H2,H3:%d\n", slinkedlist_intersect(H2, H3));
printf("========end==========\n");
/* 注意释放的时候相交链表可能会有问题，这里要让他们不再相交 */
p1->next = temp;
slinkedlist_show(H1);
slinkedlist_show(H2);
slinkedlist_show(H3);
printf("========free==========\n");
H1 = slinkedlist_free(H1);
H2 = slinkedlist_free(H2);
H3 = slinkedlist_free(H3);
}2. slinkedlist.h
c
/** ==== ==== ==== ==== ==== ==== ==== ==== ==== ==== ==== ==== ==== =
* Copyright © hk. 2022-2025. All rights reserved.
* File name : slinkedlist.h
* Author : qidaink
* Date : 2022-10-21
* Version :
* Description:
* Others :
* Log :
* ==== ==== ==== ==== ==== ==== ==== ==== ==== ==== ==== ==== ==== ==
*/
#ifndef __SLINKEDLIST_H__
#define __SLINKEDLIST_H__
/* 自定义数据类型 */
typedef int data_t;
typedef struct __node
{
data_t data;
struct __node *next;
} _slinkednode, *_slinkedlink;
/* 函数声明 */
_slinkedlink slinkedlist_create(void); /* 单链表创建 */
_slinkedlink slinkedlist_free(_slinkedlink H); /* 单链表空间释放（释放整个单链表占用的内存空间） */
int slinkedlist_show(_slinkedlink H); /* 单链表数据显示 */
_slinkedlink slinkedlist_node_get(_slinkedlink H, int pos); /* 单链表节点查找（按位置查找） */
int slinkedlist_tail_insert(_slinkedlink H, data_t value); /* 单链表尾部插入数据 */
int slinkedlist_insert(_slinkedlink H, data_t value, int pos); /* 单链表在指定位置插入节点 */
int slinkedlist_delete(_slinkedlink H, int pos); /* 删除指定位置节点 */
int slinkedlist_node_update(_slinkedlink H, data_t value, int pos); /* 更新指定位置的节点数据 */
int slinkedlist_length(_slinkedlink H); /* 获取单链表长度（不包含头节点） */
int slinkedlist_reverse_insertH(_slinkedlink H); /* 头插法反转单链表 */
_slinkedlink slinkedlist_reverse_iteration(_slinkedlink H); /* 迭代法反转链表 */
_slinkedlink slinkedlist_reverse_recursiveH(_slinkedlink H); /* 递归法反转单链表 */
_slinkedlink slinkedlist_reverse_recursive(_slinkedlink H); /* 递归法反转单链表递归实现 */
_slinkedlink slinkedlist_reverse_local(_slinkedlink H); /* 本地逆置法反转单链表 */
_slinkedlink slinkedlist_bubble_sort(_slinkedlink H, int mode); /* 单链表排序（冒泡法排序) */
int slinkedlist_intersect(_slinkedlink H1, _slinkedlink H2); /* 判断两链表是否相交 */
_slinkedlink slinkedlist_adjmax(_slinkedlink H, data_t *value); /* 求相邻两节点和最大时的第一个节点指针 */
int test_slinkedlist_tail_insert(); /* 单链表尾部插入测试 */
void test_slinkedlist_node_get(); /* 节点查找测试 */
void test_slinkedlist_insert(); /* 指定位置插入测试 */
void test_slinkedlist_delete(); /* 按位置删除节点测试 */
void test_slinkedlist_node_update(); /* 更新节点数据测试 */
void test_slinkedlist_length(); /* 获取链表长度测试 */
void test_slinkedlist_reverse_iteration(); /* 迭代法反转单链表测试 */
void test_slinkedlist_reverse_recursiveH(); /* 递归法反转单链表测试 */
void test_slinkedlist_reverse_insertH(); /* 头插法反转单链表测试 */
void test_slinkedlist_reverse_local(); /* 本地逆置法反转单链表测试 */
void test_slinkedlist_bubble_sort(); /* 冒泡法链表排序测试 */
void test_slinkedlist_adjmax(); /* 求相邻两节点和最大时的第一个节点指针测试 */
void test_slinkedlist_intersect(); /* 判断两链表是否相交测试 */
#endif3. main.c
c
#include <stdio.h>
#include "slinkedlist.h"
int main(int argc, char *argv[])
{
// test_slinkedlist_tail_insert();
// test_slinkedlist_node_get();
// test_slinkedlist_insert();
// test_slinkedlist_delete();
// test_slinkedlist_node_update();
// test_slinkedlist_length();
// test_slinkedlist_reverse_iteration();
// test_slinkedlist_reverse_recursiveH();
// test_slinkedlist_reverse_insertH();
// test_slinkedlist_reverse_local();
test_slinkedlist_bubble_sort();
// test_slinkedlist_adjmax();
// test_slinkedlist_intersect();
return 0;
}4. Makefile
makefile
##============================================================================#
# Copyright © hk. 2022-2025. All rights reserved.
# File name : Makefile
# Author : qidaink
# Date : 2022-09-29
# Version :
# Description:
# Others :
# Log :
##============================================================================#
##
TARGET := main
#============================================================================#
## 工具设置
# 设置交叉编译器名称
CROSS_COMPILE :=
# 设置交叉编译器
CC := $(CROSS_COMPILE)gcc
# 编译选项
CFLAGS += -g -Wall
#============================================================================#
## 目录路径设置
# 头文件路径设置(.h)
INCDIRS := .
# 源文件路径设置(.S .C)
SRCDIRS := .
# 生成的中间 .o 文件的位置
OBJDIRS := .
#============================================================================#
# 生成编译器的 -I dir_path 参数
INCLUDE := $(patsubst %, -I %, $(INCDIRS))
# 获取所有的 .C 文件名称(包含路径)
CFILES := $(foreach dir, $(SRCDIRS), $(wildcard $(dir)/*.c))
# 获取所有的 .C 文件名称(不包含路径)
CFILENDIR := $(notdir $(CFILES))
# 指定所有的 .C 生成的 .o 文件名(包含将要存放的路径)
COBJS := $(patsubst %, $(OBJDIRS)/%, $(CFILENDIR:.c=.o))
# 将所有要生成的 .o 文件合并到一个变量中(都包含路径)
OBJS := $(COBJS)
# 设置源文件路径
VPATH := $(SRCDIRS)
#============================================================================#
# 生成目标文件
$(TARGET): $(OBJS)
$(CC) $(CFLAGS) $^ -o $(TARGET)
# 隐含规则推导相关中间文件
$(COBJS) : $(OBJDIRS)/%.o : %.c
$(CC) $(CFLAGS) -c $(INCLUDE) $< -o $@
#============================================================================#
.PHONY: clean clean_o
# 删除所有编译链接生成的文件命令
clean: clean_o
@rm -vf $(TARGET)
# 删除所有的 .o 文件命令
clean_o:
@rm -vf $(COBJS)
printf:
@echo "CFLAGS = $(CFLAGS)"
@echo "INCDIRS = $(INCDIRS)"
@echo "SRCDIRS = $(SRCDIRS)"
@echo "INCLUDE = $(INCLUDE)"
@echo "CFILES = $(CFILES)"
@echo "CFILENDIR = $(CFILENDIR)"
@echo "COBJS = $(COBJS)"
@echo "OBJS = $(OBJS)"
@echo "VPATH = $(VPATH)"