最近有很多同学在学习链表，因此特地出一期详细的链表教学，当然最重要的还是自己**亲手敲一遍**才能深刻理解。最好还能跟**上手画草图**，可以更好的理解链表的实现过程。
相信既然学到链表应该都对函数有所了解，因此今天以函数的形式来进行操作，同时**大部分解释以注释的形式与代码在一起**。
那么话不多说，直接进入今天的主题——单链表。
主要函数malloc、free
malloc函数是包含于stdlib.h头文件下的一个库函数，其作用是在堆区申请开辟一块空间，如果不理解的话，可以简单理解为malloc创建出来之后在程序结束之前就不会消失，相当于全局变量。其用法如下：
void* malloc (size_t size);分配内存块
分配一个字节内存块，返回指向该块开头的指针。
新分配的内存块的内容未初始化，剩余为不确定值。
如果为零，则返回值取决于特定的库实现（它可能是空指针，也可能不是空指针），但不应取消引用返回的指针。
括号内的即为开辟空间的大小，以字节为单位，如int类型为4.
free同样包含于stdlib.h头文件下，其作用是释放malloc开辟的空间。很多同学并不理解，认为实际上很多时候忘记加free也没有出现bug，但是建议养成一个良好的习惯。假设有一台服务器，需要存放玩家数据，每次都是用malloc分配，如果数据不用之后不对其空间进行free，那么长久下来，系统的堆区就变得很小，导致了卡顿，雀氏重启可以自动释放，但是对于一个需要持续运行的服务器，每隔几天重启一次，那么已经存放的玩家数据怎么办？所以希望同学们能重视这一个细节
void free (void* ptr);解除分配内存块
释放先前由malloc等调用分配的内存块，使其再次可用于进一步分配。
如果不指向为上述函数分配的内存块，则会导致未定义的行为。
if 是空指针，则该函数不执行任何操作。
尾插法
头插法
#include<stdio.h>
#include<stdlib.h>
typedef struct linklist //结构体的定义
{
int num; //数据域
struct linklist* next; //指针域
}list;
list* list_make(list* head, int length); //函数的声明
int main()
{
int length = 0; //用于输入链表期望的长度
list* head = (list*)malloc(sizeof(list)); //开辟空间时，将malloc返回的指针强制转换为结构体的指针
scanf("%d", &length);
head = list_make(head, length);
list* head0 = NULL; //用于代替头节点的移动
head0 = head->next; //通常头结点不用于存放数据，当然也可以存放，看个人习惯
while (head0 != NULL)
{
printf("%d", head0->num);
head0 = head0->next;
}
return 0;
}
list* list_make(list* head, int length) //list*类型的函数，返回一个结构体指针
{
int i = 0; //相比于尾插法，头插法不需要记录头指针的位置，因为头指针的不断更新的
head->next = NULL; //循环开始之前head就是链表的末尾，此操作为将链表末尾设置为NULL，标志链表的结束
for (i = 0; i < length; i++)
{
scanf("%d", &head->num); //输入数据,将输入放在这里是为了更好的体现头插法的特点-》不断向前申请结点
list* node = (list*)malloc(sizeof(list)); //创建一个结点
node->next = head; //该结点在head的后面，也就是head->next
head = node; //将head向后移动到新的结点的位置，然后重复上述步骤
}
return head; //返回头节点
}
增加结点
#include<stdio.h>
#include<stdlib.h>
typedef struct linklist //结构体的定义
{
int num; //数据域
struct linklist* next; //指针域
}list;
list* list_make(list* head, int length); //函数的声明
list* list_add(list* head, int n);
int main()
{
int n; //用于输入想增加的结点的位置
scanf("%d", &n); //注意范围为 0 <= n <= length
list* head = (list*)malloc(sizeof(list));
head = list_make(head, 10); //先用头插法创建一个长度为10的链表，其中降序存放0-9
head = list_add(head, n);
list* head0 = NULL; //用于代替头节点的移动
head0 = head->next; //通常头结点不用于存放数据，当然也可以存放，看个人习惯
while (head0 != NULL)
{
printf("%d ", head0->num);
head0 = head0->next;
}
return 0;
}
list* list_make(list* head, int length)
{
int i = 0;
head->next = NULL;
for (i = 0; i < length; i++)
{
head->num = i;
list* node = (list*)malloc(sizeof(list));
node->next = head;
head = node;
}
return head;
}
list* list_add(list* head, int n)
{
list* head0 = head; //代替头指针的移动
for (; n; n--) //移动到需要增加的结点处
{
//例如要在第 n 个结点出增加结点，由于头结点不含数据，因此移动n次即第n个结点
head0 = head0->next;
}
list* node = (list*)malloc(sizeof(list)); //申请开辟空间
scanf("%d", &node->num);
node->next = head0->next;
head0->next = node; //顺序不要错了，不然会丢失掉第n + 1个结点的位置哦
return head;
}
** 总结起来，头插法存放数据是逆序，尾插法则是正序**
删除结点
正序删除第n个结点
移除链表元素 - 力扣（LeetCode） (leetcode-cn.com)
删除链表中的节点 - 力扣（LeetCode） (leetcode-cn.com)
#include<stdio.h>
#include<stdlib.h>
typedef struct linklist //结构体的定义
{
int num; //数据域
struct linklist* next; //指针域
}list;
list* list_make(list* head, int length); //函数的声明
list* list_delete(list* head, int n);
int main()
{
int n; //用于输入想删除的结点的位置
scanf("%d", &n);
list* head = (list*)malloc(sizeof(list));
head = list_make(head, 10); //先用头插法创建一个长度为10的链表，其中降序存放0-9
head = list_delete(head, n);
list* head0 = NULL; //用于代替头节点的移动
head0 = head->next; //通常头结点不用于存放数据，当然也可以存放，看个人习惯
while (head0 != NULL)
{
printf("%d", head0->num);
head0 = head0->next;
}
return 0;
}
list* list_make(list* head, int length)
{
int i = 0;
head->next = NULL;
for (i = 0; i < length; i++)
{
head->num = i;
list* node = (list*)malloc(sizeof(list));
node->next = head;
head = node;
}
return head;
}
list* list_delete(list* head, int n)
{
list* head0 = head; //代替头指针的移动
for (--n; n; n--) //删除结点的时候需要移动到该结点前一个结点
{
//例如要删除第 n 个结点,则在第n - 1个结点处停下，到这里或许你能理解为什么说头节点通常不存放数据了
//该循环的意思是先将n-1，表示整个过程需要移动n-1下，判断条件n是n不为0,就是说n不断-1,直到为0就移动到第n-1个结点了
head0 = head0->next;
}
list* node = head0->next; //记录下需要删除的结点的位置
head0->next = node->next;
//此处是最容易发生错误的，很多初学者会将指针移动到正好第n个结点，然后head = head->next
//乍一看两者一样，但是head = head->next是head这一个指针的移动，而实际上各个指针域并没有发生改变
//但是head0->next = node->next 是一个对head0->next的赋值操作，也就是改变了head0的指针域
free(node); //释放掉之前该结点malloc申请的空间
return head;
}
** 关键：移动到第n - 1个结点**
逆序删除第n个结点
- 删除链表的倒数第 N 个结点 - 力扣（LeetCode） (leetcode-cn.com)
常规删除（遍历链表两遍）
#include<stdio.h>
#include<stdlib.h>
typedef struct linklist //结构体的定义
{
int num; //数据域
struct linklist* next; //指针域
}list;
list* list_make(list* head, int length); //函数的声明
list* list_delete(list* head, int n);
int main()
{
int n; //用于输入想逆序删除的结点的位置
scanf("%d", &n);
list* head = (list*)malloc(sizeof(list));
head = list_make(head, 10); //先用头插法创建一个长度为10的链表，其中降序存放0-9
head = list_delete(head, n);
list* head0 = NULL; //用于代替头节点的移动
head0 = head->next; //通常头结点不用于存放数据，当然也可以存放，看个人习惯
while (head0 != NULL)
{
printf("%d", head0->num);
head0 = head0->next;
}
return 0;
}
list* list_make(list* head, int length)
{
int i = 0;
head->next = NULL;
for (i = 0; i < length; i++)
{
head->num = i;
list* node = (list*)malloc(sizeof(list));
node->next = head;
head = node;
}
return head;
}
list* list_delete(list* head, int n)
{
int length = 0; //用于记录链表的长度
list* head0 = head->next; //代替头指针的移动
while (head0 != NULL)
{
++length; //head0每移动一次length就+1,最后可以得出链表的长度
head0 = head0->next;
}
for (head0 = head, length -= n; length; length--) //将head0指向head, 循环其余设可以参考正序删除第n个结点的设置
{
//倒数第n个就是正数第length-n+1个结点，举例：length = 10, n = 2, 那么就是第 10-2+1=9第9个结点
head0 = head0->next;
}
list* node = head0->next;
head0->next = node->next;
free(node);
return head;
}
存入结构体指针数组（遍历链表一遍）
#include<stdio.h>
#include<stdlib.h>
typedef struct linklist //结构体的定义
{
int num; //数据域
struct linklist* next; //指针域
}list;
list* list_make(list* head, int length); //函数的声明
list* list_delete(list* head, int n);
int main()
{
int n; //用于输入想逆序删除的结点的位置
scanf("%d", &n);
list* head = (list*)malloc(sizeof(list));
head = list_make(head, 10); //先用头插法创建一个长度为10的链表，其中降序存放0-9
head = list_delete(head, n);
list* head0 = NULL; //用于代替头节点的移动
head0 = head->next; //通常头结点不用于存放数据，当然也可以存放，看个人习惯
while (head0 != NULL)
{
printf("%d", head0->num);
head0 = head0->next;
}
return 0;
}
list* list_make(list* head, int length)
{
int i = 0;
head->next = NULL;
for (i = 0; i < length; i++)
{
head->num = i;
list* node = (list*)malloc(sizeof(list));
node->next = head;
head = node;
}
return head;
}
#define my_max 100
list* list_delete(list* head, int n)
{
list* arr[my_max], * head0 = head;
//建立一个结构体指针数组保存各个结点的位置，head0来遍历链表
int i = 0;
while (head0 != NULL)
{
arr[i] = head0;
i++;// i用于记录结点个数，但要注意会把头结点记录进去（我的头结点未存放数据）
head0 = head0->next;//head0向后移动
}
arr[i] = head0; //最后将NULL记录入数组
arr[i - n - 1]->next = arr[i - n + 1]; //直接利用数组记录结点进行操作，不用再次遍历
free(arr[i - n]); // 记得释放空间
return head;
}
动态规划滑动窗口双指针（遍历链表一遍）
#include<stdio.h>
#include<stdlib.h>
typedef struct linklist //结构体的定义
{
int num; //数据域
struct linklist* next; //指针域
}list;
list* list_make(list* head, int length); //函数的声明
list* list_delete(list* head, int n);
int main()
{
int n; //用于输入想逆序删除的结点的位置
scanf("%d", &n);
list* head = (list*)malloc(sizeof(list));
head = list_make(head, 10); //先用头插法创建一个长度为10的链表，其中降序存放0-9
head = list_delete(head, n);
list* head0 = NULL; //用于代替头节点的移动
head0 = head->next; //通常头结点不用于存放数据，当然也可以存放，看个人习惯
while (head0 != NULL)
{
printf("%d", head0->num);
head0 = head0->next;
}
return 0;
}
list* list_make(list* head, int length)
{
int i = 0;
head->next = NULL;
for (i = 0; i < length; i++)
{
head->num = i;
list* node = (list*)malloc(sizeof(list));
node->next = head;
head = node;
}
return head;
}
#define my_max 100
list* list_delete(list* head, int n)
{
list* r = NULL, * l = NULL; //设置两个左右指针
r = head, l = head; //先置于头结点
while (n--)
r = r->next; //r移动n个结点，此时l - r之间存在n个结点
while (r->next)
{
r = r->next;
l = l->next;
// r, l均向后移，直到r的下一个结点是链表末尾，此时由于l - r之间存在n个结点
//因此r恰好指向到数第n + 1个结点
}
r = l->next;//r此时记录下需要释放内存的地点
l->next = l->next->next; //删除节点
free(r); //释放内存
return head;
}
交换结点
#include<stdio.h>
#include<stdlib.h>
typedef struct linklist //结构体的定义
{
int num; //数据域
struct linklist* next; //指针域
}list;
list* list_make(list* head, int length); //函数的声明
list* list_exchange(list* head, int a, int b);
int main()
{
int a, b; //用于输入想增加的结点的位置
scanf("%d%d", &a, &b);
list* head = (list*)malloc(sizeof(list));
head = list_make(head, 10); //先用头插法创建一个长度为10的链表，其中降序存放0-9
head = list_exchange(head, a, b);
list* head0 = NULL; //用于代替头节点的移动
head0 = head->next; //通常头结点不用于存放数据，当然也可以存放，看个人习惯
while (head0 != NULL)
{
printf("%d ", head0->num);
head0 = head0->next;
}
return 0;
}
list* list_make(list* head, int length)
{
int i = 0;
head->next = NULL;
for (i = 0; i < length; i++)
{
head->num = i;
list* node = (list*)malloc(sizeof(list));
node->next = head;
head = node;
}
return head;
}
list* list_exchange(list* head, int a, int b)
{
if (a > b) //统一大小顺序，方便交换
{
int t = a;
a = b;
b = t;
}
int i = 0;
list* head0 = head, * exc1 = NULL, * exc2 = NULL; //代替头指针的移动
while (head0) //移动到需要增加的结点处
{
if (i + 1 == a)
exc1 = head0;
if (i + 1 == b)
exc2 = head0; //分别找到需要交换的两个结点的前一个结点
i++;
head0 = head0->next;
}
list* a1 = exc1, * a2 = exc1->next->next, * b1 = exc2, * b2 = exc2->next->next; //几下两个结点左右的结点
exc1 = exc1->next, exc2 = exc2->next;//将exc1,exc2变为被交换的结点，此方法最笨，但是最容易理解掌握
if (abs(a - b) != 1)//相邻结点的交换与不相邻的结点交换不同
{
a1->next = exc2, exc2->next = a2, b1->next = exc1, exc1->next = b2;
}
else
{
a1->next = exc2, exc2->next = exc1, exc1->next = b2;
}
return head;
}
倒序输出数据域（采用存入一个大数组中）
#include<stdio.h>
#include<stdlib.h>
typedef struct linklist //结构体的定义
{
int num; //数据域
struct linklist* next; //指针域
}list;
list* list_make(list* head, int length); //函数的声明
void list_reprintf(list* head);
int main()
{
list* head = (list*)malloc(sizeof(list));
head = list_make(head, 10); //先用头插法创建一个长度为10的链表，其中降序存放0-9
list* head0 = NULL; //用于代替头节点的移动
head0 = head->next; //通常头结点不用于存放数据，当然也可以存放，看个人习惯
printf("链表原本为："); //打印原链表顺序，方便对比
while (head0 != NULL)
{
printf("%d", head0->num);
head0 = head0->next;
}
printf("\n");
list_reprintf(head);
return 0;
}
list* list_make(list* head, int length)
{
int i = 0;
head->next = NULL;
for (i = 0; i < length; i++)
{
head->num = i;
list* node = (list*)malloc(sizeof(list));
node->next = head;
head = node;
}
return head;
}
#define my_max 100
void list_reprintf(list* head)
{
printf("逆序输出为：");
int arr[my_max] = { 0 }, i = 0; //定义一个大数组（元素大于给出链表的结点上限）
list* head0 = head->next; // 用head0来代替头指针移动，防止head指向位置发生改变而找不到头结点
while (head0)
{
arr[i++] = head0->num; //顺序存入数组
head0 = head0->next;
}
while (i)
printf("%d", arr[--i]); //i此时为元素上限，逆序输出数组即可
}
升序链表合并
两个升序链表合并
- 合并两个有序链表 - 力扣（LeetCode） (leetcode-cn.com)
正常逐个判断
#include<stdio.h>
#include<stdlib.h>
typedef struct linklist //结构体的定义
{
int num; //数据域
struct linklist* next; //指针域
}list;
list* list_make(list* head, int length); //函数的声明
list* list_merge(list* head1, list* head2);
int main()
{
int length = 0; //用于输入链表期望的长度
list* head1 = (list*)malloc(sizeof(list));
scanf("%d", &length);
head1 = list_make(head1, length);//创建链表1
list* head2 = (list*)malloc(sizeof(list));
scanf("%d", &length);
head2 = list_make(head2, length);//创建链表2
list* head = list_merge(head1->next, head2->next); //合并的时候从有数据的开始，因此传入头结点之后的一个结点
while (head->next)
{
head = head->next;
printf("%d\n", head->num);
}
return 0;
}
list* list_make(list* head, int length) //list*类型的函数，返回一个结构体指针
{
int i = 0;
list* head0 = head; //创建一个head0来记录head头节点的位置，便于返回
for (i = 0; i < length; i++)
{
list* node = (list*)malloc(sizeof(list)); //创建一个结点
head->next = node; //该结点在head的后面，也就是head->next
head = node; //将head向后移动到新的结点的位置，然后重复上述步骤
scanf("%d", &head->num);
}
head->next = NULL; //循环结束后head应该在链表的末尾，此操作为将链表末尾设置为NULL，标志链表的结束
return head0; //返回头节点
}
list* list_merge(list* head1, list*head2)
{
list* head = (list*)malloc(sizeof(list)); //创建一个新的头结点作为合并后的新头结点
list* head0 = head; //记录下头结点的位置
while (head1 && head2) //只要一个链表到达尾部，即停止
{
if (head1->num >= head2->num) //比较并衔接
{
head->next = head2;
head2 = head2->next;
}
else if (head1->num < head2->num)
{
head->next = head1;
head1 = head1->next;
}
head = head->next;
}
if (head1 == NULL) //到达尾部之后只需把另一个链表衔接到尾部即可
head->next = head2;
else if (head2 == NULL)
head->next = head1;
return head0;
}
递归
#include<stdio.h>
#include<stdlib.h>
typedef struct linklist //结构体的定义
{
int num; //数据域
struct linklist* next; //指针域
}list;
list* list_make(list* head, int length); //函数的声明
list* list_merge(list* head1, list* head2);
int main()
{
int length = 0; //用于输入链表期望的长度
list* head1 = (list*)malloc(sizeof(list));
scanf("%d", &length);
head1 = list_make(head1, length);//创建链表1
list* head2 = (list*)malloc(sizeof(list));
scanf("%d", &length);
head2 = list_make(head2, length);//创建链表2
return 0;
}
list* list_make(list* head, int length) //list*类型的函数，返回一个结构体指针
{
int i = 0;
list* head0 = head; //创建一个head0来记录head头节点的位置，便于返回
for (i = 0; i < length; i++)
{
list* node = (list*)malloc(sizeof(list)); //创建一个结点
head->next = node; //该结点在head的后面，也就是head->next
head = node; //将head向后移动到新的结点的位置，然后重复上述步骤
scanf("%d", &head->num);
}
head->next = NULL; //循环结束后head应该在链表的末尾，此操作为将链表末尾设置为NULL，标志链表的结束
return head0; //返回头节点
}
list* list_merge(list* head1, list*head2)
{
if (head1 == NULL) //遇到NULL则直接返回另一个链表剩下的即可
return head2;
if (head2 == NULL)
return head1;
if (head1->num < head2->num) //head1 < head2注定返回head1
{
head1->next = list_merge(head1->next, head2); //递归判断下一个结点
return head1;
}
else
{
head2->next = list_merge(head1, head2->next);
return head2;
}
}
K个正序链表合并
- 合并K个升序链表 - 力扣（LeetCode） (leetcode-cn.com)
同时判断k个数字（时间最长）
#include<stdio.h>
#include<stdlib.h>
typedef struct linklist //结构体的定义
{
int num; //数据域
struct linklist* next; //指针域
}list;
list* list_make(list* head, int length); //函数的声明
list* list_merge(list** lists, int size);
int main()
{
list* node[10];
int x = 0, y = 0, i = 0; //用于输入链表期望的长度
scanf("%d", &x);
for (i = 0; i < x; i++)
{
scanf("%d", &y);
node[i] = (list*)malloc(sizeof(list));
node[i] = list_make(node[i], y); //创建链表
}
list* head = list_merge(node, x);
while (head && head->next)
{
head = head->next;
printf("%d\n", head->num);
}
printf("NULL");
return 0;
}
list* list_make(list* head, int length) //list*类型的函数，返回一个结构体指针
{
if (length == 0)
return NULL;
int i = 0;
list* head0 = head; //创建一个head0来记录head头节点的位置，便于返回
for (i = 0; i < length - 1; i++) //由于要从头结点开始记录数据，故循环次数-1
{
scanf("%d", &head->num);
list* node = (list*)malloc(sizeof(list)); //创建一个结点
head->next = node; //该结点在head的后面，也就是head->next
head = node; //将head向后移动到新的结点的位置，然后重复上述步骤
}
scanf("%d", &head->num); // 输入最后一个结点的数据
head->next = NULL;
return head0; //返回头节点
}
list* list_merge(list** lists, int size)
{
list* head = (list*)malloc(sizeof(list)); //首先创建一个头结点
if (size == 0) //如果size为0，返回NULL
return NULL;
else if (size == 1) //如果只有一个链表，直接返回该链表
{
head->next = lists[0];
return head;
}
int i = 0, k = 0; //i用于遍历每一个链表的第一个值，k用于保存是哪一条链表
list* head0 = head, * p = NULL;
while (1) //死循环的意思
{
for (p = NULL, i = 0; i < size; i++) //每次先将p赋值为lists中第一个有效的值
if (lists[i])
p = lists[i];
if (!p) //如果没有找到有效的值，说明所有链表以及遍历完成，返回head0
{
head->next = NULL;
return head0;
}
for (i = 0; i < size; i++)
{
if (lists[i])
p = p->num < lists[i]->num ? p :(k = i, lists[i]); //三目运算符与逗号表达式
}
if (lists[i] != NULL)
{
list* node = (list*)malloc(sizeof(list)); //创建一个结点来保存新的数据
head->next = node;
head = head->next;
head->num = p->num; //将p记录的结点的数据赋值给到新链表
lists[k] = lists[k]->next; //数据被使用的链表向后移动一个结点
}
}
}
先合并两个链表，再不断将得到的新链表与其他链表合并（时间较长，优化较小）
#include<stdio.h>
#include<stdlib.h>
typedef struct linklist //结构体的定义
{
int num; //数据域
struct linklist* next; //指针域
}list;
list* list_make(list* head, int length); //函数的声明
list* list_merge_of_two(list* head1, list* head2);
list* list_merge_of_k(list** lists, int size);
int main()
{
list* node[10];
int x = 0, y = 0, i = 0; //用于输入链表期望的长度
scanf("%d", &x);
for (i = 0; i < x; i++)
{
scanf("%d", &y);
node[i] = (list*)malloc(sizeof(list));
node[i] = list_make(node[i], y); //创建链表
}
list* head = list_merge_of_k(node, x);
while (head && head->next)
{
head = head->next;
printf("%d ", head->num);
}
printf("NULL");
return 0;
}
list* list_make(list* head, int length) //list*类型的函数，返回一个结构体指针
{
if (length == 0)
return NULL;
int i = 0;
list* head0 = head; //创建一个head0来记录head头节点的位置，便于返回
for (i = 0; i < length - 1; i++) //由于要从头结点开始记录数据，故循环次数-1
{
scanf("%d", &head->num);
list* node = (list*)malloc(sizeof(list)); //创建一个结点
head->next = node; //该结点在head的后面，也就是head->next
head = node; //将head向后移动到新的结点的位置，然后重复上述步骤
}
scanf("%d", &head->num); // 输入最后一个结点的数据
head->next = NULL;
return head0; //返回头节点
}
list* list_merge_of_two(list* head1, list* head2)
{
list* head = (list*)malloc(sizeof(list));
list* head0 = head;
while (head1 || head2)
{
list* head = (list*)malloc(sizeof(list)); //创建一个新的头结点作为合并后的新头结点
list* head0 = head; //记录下头结点的位置
while (head1 && head2) //只要一个链表到达尾部，即停止
{
if (head1->num >= head2->num) //比较并衔接
{
head->next = head2;
head2 = head2->next;
}
else if (head1->num < head2->num)
{
head->next = head1;
head1 = head1->next;
}
head = head->next;
}
if (head1 == NULL) //到达尾部之后只需把另一个链表衔接到尾部即可
head->next = head2;
else if (head2 == NULL)
head->next = head1;
return head0;
}
}
list* list_merge_of_k(list** lists, int size)
{
list* fin = (list*)malloc(sizeof(list)); //创建新链表的头结点
if (size == 0)
return NULL;
else if (size == 1)
{
fin->next = lists[0];
return fin;
}
int i = 2;
fin = list_merge_of_two(lists[0], lists[1]); //先将两条链表合并
//在此调用之前写的合并两个链表的函数
while (i < size)
{
fin = list_merge_of_two(fin->next, lists[i]);
//逐一将剩下的链表合并进来，注意两个链表合并是从有数据的头结点开始的
i++;
}
return fin;
}
每两个链表为一组，不断向下合成新链表（时间最短，优化巨大）
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
typedef struct linklist //结构体的定义
{
int num; //数据域
struct linklist* next; //指针域
}list;
list* list_make(list* head, int length); //函数的声明
list* list_merge_of_two(list* head1, list* head2);
list* list_merge_of_k(list** lists, int size);
int main()
{
list* node[10];
int x = 0, y = 0, i = 0; //用于输入链表期望的长度
scanf("%d", &x);
for (i = 0; i < x; i++)
{
scanf("%d", &y);
node[i] = (list*)malloc(sizeof(list));
node[i] = list_make(node[i], y); //创建链表
}
list* head = list_merge_of_k(node, x);
while (head && head->next)
{
head = head->next;
printf("%d ", head->num);
}
printf("NULL");
return 0;
}
list* list_make(list* head, int length) //list*类型的函数，返回一个结构体指针
{
if (length == 0)
return NULL;
int i = 0;
list* head0 = head; //创建一个head0来记录head头节点的位置，便于返回
for (i = 0; i < length - 1; i++) //由于要从头结点开始记录数据，故循环次数-1
{
scanf("%d", &head->num);
list* node = (list*)malloc(sizeof(list)); //创建一个结点
head->next = node; //该结点在head的后面，也就是head->next
head = node; //将head向后移动到新的结点的位置，然后重复上述步骤
}
scanf("%d", &head->num); // 输入最后一个结点的数据
head->next = NULL;
return head0; //返回头节点
}
list* list_merge_of_two(list* head1, list* head2)
{
list* head = (list*)malloc(sizeof(list));
list* head0 = head;
while (head1 || head2)
{
list* head = (list*)malloc(sizeof(list)); //创建一个新的头结点作为合并后的新头结点
list* head0 = head; //记录下头结点的位置
while (head1 && head2) //只要一个链表到达尾部，即停止
{
if (head1->num >= head2->num) //比较并衔接
{
head->next = head2;
head2 = head2->next;
}
else if (head1->num < head2->num)
{
head->next = head1;
head1 = head1->next;
}
head = head->next;
}
if (head1 == NULL) //到达尾部之后只需把另一个链表衔接到尾部即可
head->next = head2;
else if (head2 == NULL)
head->next = head1;
return head0;
}
}
list* list_merge_of_k(list** lists, int size)
{
list* fin[10000];//创建一个数组存放合并之后的各个新链表头结点
if (size == 0)
return NULL;
else if (size == 1)
{
fin[0] = (list*)malloc(sizeof(list));
fin[0]->next = lists[0];
return lists[0];
int i = 0, all = size;
while (i < all)
fin[i++] = lists[i];//先将链表均存放入数组
while (all != 1)
{
i = 0;
while (i < all / 2)
{
fin[i] = list_merge_of_two(fin[2 * i], fin[2 * i + 1]);
//继续调用合并两个链表的函数
//每次相邻的两个合并到i中,由于两个一合并，所以存入i不会引发冲突
i++;
}
if (all % 2)//判断当前余下的新链表（奇数时最后一个链表会多出来）
{
fin[i] = fin[all - 1];//存入最后一个数组
all = (all + 1) / 2;
}
else
all /= 2;
}
return fin[0];//最后所有数组合并到fin[0]
}
翻转链表
整个链表反转，如123变为321
- 反转链表 - 力扣（LeetCode） (leetcode-cn.com)
#include<stdio.h>
#include<stdlib.h>
typedef struct linklist //结构体的定义
{
int num; //数据域
struct linklist* next; //指针域
}list;
list* list_make(list* head, int length); //函数的声明
list* list_reverse_by_total(list* head, list* tail);
int main()
{
list* head = (list*)malloc(sizeof(list));
head = list_make(head, 10); //先用头插法创建一个长度为10的链表，其中降序存放0-9
list* head0 = NULL; //用于寻找尾结点
while (head0 != NULL)
head0 = head0->next; //找到该链表的尾节点
head0 = list_reverse_by_total(head->next, head0);
while (head0 != NULL)
{
printf("%d ", head0->num);
head0 = head0->next;
}
return 0;
}
list* list_make(list* head, int length)
{
int i = 0;
head->next = NULL;
for (i = 0; i < length; i++)
{
head->num = i;
list* node = (list*)malloc(sizeof(list));
node->next = head;
head = node;
}
return head;
}
list* list_reverse_by_total(list* a, list* b) //给定头指针和尾指针，将整个链表翻转
{
list* tail = NULL; //默认将翻转后链表的尾指针指向NULL
list* mid = a;
list* head = a;
while (mid != b)
{
head = mid->next;
//整个过程就是head先根据mid找到下一个结点，然后mid不断指向head，最后tail,mid依次后移，重复过程
mid->next = tail;
tail = mid;
mid = head;
}
return tail; //mid和head最后都指向下一组的头结点，而mid则是实际上这一组的头结点
}
k个为一组，翻转链表
两两交换链表中的节点 - 力扣（LeetCode） (leetcode-cn.com)
合并K个升序链表 - 力扣（LeetCode） (leetcode-cn.com)
较复杂但相对比较容易理解想到
#include<stdio.h>
#include<stdlib.h>
typedef struct linklist //结构体的定义
{
int num; //数据域
struct linklist* next; //指针域
}list;
list* list_make(list* head, int length); //函数的声明
list* list_reverse_k(list* head, int k);
list* list_reverse_two(list* head);
int main()
{
int length = 0, n = 0; //链表的长度与多少个为一组翻转
scanf("%d%d", &length, &n);
list* head = (list*)malloc(sizeof(list));
head = list_make(head, length);
head = list_reverse_k(head->next, n);//传入有数据的头结点
while (head)
{
printf("%d ", head->num);
head = head->next;
}
printf("NULL");
return 0;
}
list* list_make(list* head, int length)
{
int i = 0;
list* head0 = head;
for (i = 0; i < length; i++)
{
list* node = (list*)malloc(sizeof(list));
head->next = node;
head = node;
head->num = i;
}
head->next = NULL;
return head0;
}
list* list_reverse_k(list* head, int k)
{
if (k == 1 || head == NULL)
return head;
if (k == 2)
return list_reverse_two(head); //本代码无法单独解决两个一组反转，因此另写一组函数
int i = 0;
list* new_head = head, * last_tail = head, * l = head, * m = head->next, * r = head->next->next, * head0 = NULL;
for (i = 0; i < k && new_head; i++)
new_head = new_head->next;//确保剩下的可以翻转，并找到下一组的起点
if (i != k)
return head;//总结点的不满足k的情况
for (i = 3; i < k; i++)
{
m->next = l; //m不断向后指向l,r不断顺链表移动
l = m;
m = r;
r = r->next;
}
r->next = m;
m->next = l;//最后再将r，m,l连接，这也就是为什么本代码无法单独解决两个一组的翻转
head0 = r; //单独将第一组翻转拿出来找到返回值的头结点
list* tail = NULL;//用于记录下一组翻转的链表的起点（翻转后变为终点）
while (1)
{
tail = r = m = l = new_head; //指向新的起点
for (i = 0; i < k && new_head; i++)
new_head = new_head->next;//检验剩余结点数量是否满足k
if (i != k )
break;
m = m->next, r = r->next->next;//l,m,r继续呈连续三个结点
for (i = 3; i < k; i++)//l,m,r三个结点最后相连，因此i从3开始计数
{
m->next = l;//重复上述步骤
l = m;
m = r;
r = r->next;
}
r->next = m;
m->next = l;
last_tail->next = r; //将上一组的结尾连接到这一组翻转后的起点
last_tail = tail;//同时上一组的尾指针移动到这一组翻转后的尾部，充当下一次的“上一组的尾指针”
}
last_tail->next = tail; //若不满足k或刚好满足k，都可以是看作新的一组未翻转前的起点与上一组的尾结点相连
return head0;
}
list* list_reverse_two(list* head)
{
if (head == NULL || head->next == NULL)
return head; //无法翻转的情况直接返回链表起点
list* a = head, * b = head->next, * c = head->next->next;
head = head->next; //一旦没有直接推出就可以翻转，设置head为翻转后的头结点位置
while (c != NULL && c->next != NULL) //满足此情况时，表示至少还存在两个非NULL结点，因此可以翻转
{
c = b->next;
b->next = a;
if (c != NULL && c->next != NULL) //如果c改变位置后，链表之后还存在两个非NULL结点，则继续移动a,b,否则退出
{
b = c->next;
a->next = b;
a = c;
}
}
a->next = c; //将不可翻转的剩余的部分衔接到翻转之后的链表上
return head;
}
较简单（递归）
#include<stdio.h>
#include<stdlib.h>
typedef struct linklist //结构体的定义
{
int num; //数据域
struct linklist* next; //指针域
}list;
list* list_make(list* head, int length); //函数的声明
list* list_reverse_by_total(list* a, list* b);
list* list_reverse_by_k(list* head, int k);
int main()
{
int length = 0, n = 0; //链表的长度与多少个为一组翻转
scanf("%d%d", &length, &n);
list* head = (list*)malloc(sizeof(list));
head = list_make(head, length);
head = reverseKGroup(head->next, n);//传入有数据的头结点
while (head)
{
printf("%d ", head->num);
head = head->next;
}
printf("NULL");
return 0;
}
list* list_make(list* head, int length)
{
int i = 0;
list* head0 = head;
for (i = 0; i < length; i++)
{
list* node = (list*)malloc(sizeof(list));
head->next = node;
head = node;
head->num = i;
}
head->next = NULL;
return head0;
}
list* list_reverse_by_total(list* a, list* b) //给定头指针和尾指针，将整个链表翻转（在此为一组）
{
list* tail = NULL; //默认将翻转后链表的尾指针指向NULL
list* mid = a;
list* head = a;
while (mid != b)
{
head = mid->next;
//整个过程就是head先根据mid找到下一个结点，然后mid不断指向head，最后tail,mid依次后移，重复过程
mid->next = tail;
tail = mid;
mid = head;
}
return tail; //mid和head最后都指向下一组的头结点，而mid则是实际上这一组的头结点
}
list* list_reverse_by_k(list* head, int k)
{
if (!head) //如果是空链表就直接return
return head;
list* next_head = head; //记录下一组的头结点
for (int i = 0; i < k; i++)
{
if (!next_head)
return head; //若未循环完说明就到NULL，说明不满足k个，无法翻转
next_head = next_head->next; //next_head不断移动，循环完时在下一组的头结点
}
list* head0 = reverse(head, next_head); //先完成一组找到第一组翻转后的头结点，也就是整个翻转后的头结点
head->next = reverseKGroup(next_head, k); //以下一组的头结点进入递归
return head0;
}
创作不易，希望能得到各位的三连与关注！
本文转载自: https://blog.csdn.net/qq_62306969/article/details/123958349
版权归原作者 濡 白 所有， 如有侵权，请联系我们删除。
版权归原作者 濡 白 所有， 如有侵权，请联系我们删除。