leetcode力扣刷题之——单链表详解(两万字细节讲解,头插法尾插法,删除交换,翻转)

        最近有很多同学在学习链表,因此特地出一期详细的链表教学,当然最重要的还是自己亲手敲一遍才能深刻理解。最好还能跟上手画草图,可以更好的理解链表的实现过程。
        相信既然学到链表应该都对函数有所了解,因此今天以函数的形式来进行操作,同时大部分解释以注释的形式与代码在一起
        那么话不多说,直接进入今天的主题——单链表。

目录

主要函数malloc、free

尾插法

头插法

增加结点

删除结点 

正序删除第n个结点(附 LeetCode OJ)

逆序删除第n个结点(附 LeetCode OJ)

常规删除(遍历链表两遍)

存入结构体指针数组(遍历链表一遍)

动态规划滑动窗口双指针(遍历链表一遍)

交换结点

倒序输出数据域(采用存入一个大数组中)

升序链表合并

两个升序链表合并(附 LeetCode OJ)

正常逐个判断

递归

K个正序链表合并(附 LeetCode OJ)

同时判断k个数字(时间最长)

先合并两个链表,再不断将得到的新链表与其他链表合并(时间较长,优化较小)

每两个链表为一组,不断向下合成新链表(时间最短,优化巨大)

翻转链表

整个链表反转,如123变为321(附 LeetCode OJ)

k个为一组,翻转链表(附 LeetCode OJ)

较复杂但相对比较容易理解想到

较简单(递归)

 创作不易,希望能得到各位的三连与关注!


主要函数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
#include

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
#include

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个结点

203. 移除链表元素 - 力扣(LeetCode) (leetcode-cn.com)

237. 删除链表中的节点 - 力扣(LeetCode) (leetcode-cn.com)

#include
#include

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个结点

19. 删除链表的倒数第 N 个结点 - 力扣(LeetCode) (leetcode-cn.com)

常规删除(遍历链表两遍)

#include
#include

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
#include

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
#include

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
#include

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
#include

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此时为元素上限,逆序输出数组即可
}

升序链表合并

两个升序链表合并

21. 合并两个有序链表 - 力扣(LeetCode) (leetcode-cn.com)

正常逐个判断

#include
#include

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
#include

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个正序链表合并

23. 合并K个升序链表 - 力扣(LeetCode) (leetcode-cn.com)

同时判断k个数字(时间最长)

#include
#include

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
#include

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
#include

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

206. 反转链表 - 力扣(LeetCode) (leetcode-cn.com)

#include
#include

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个为一组,翻转链表

24. 两两交换链表中的节点 - 力扣(LeetCode) (leetcode-cn.com)

23. 合并K个升序链表 - 力扣(LeetCode) (leetcode-cn.com)

较复杂但相对比较容易理解想到

#include
#include

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
#include

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;
}

 创作不易,希望能得到各位的三连与关注!

​​​​​​​

你可能感兴趣的