数据结构之单链表的应用（一）

一、移除链表元素

这里是返回一个新的头节点，newHead本质上和head是没有关系的，原head没有发生改变，所以函数定义内部不需要使用二级指针

思路1：查找值为val的节点并返回节点，删除指定位置的节点，大概代码如下：

SLTNode* SLTFind(x);
SLTErase(pos)

while(遍历链表)  -- O(N)
{
   //查找值为val的节点 -- if判断
   //删除值为val的节点 -- O(N)

可以直观的看出，该方法的时间复杂度为O（N2）,所以还有思路2

思路2：创建新链表，将原链表中部位val的节点拿下来尾插，时间复杂度为：O（N）

大概思路代码：

while(遍历原链表)
{
  //新链表中尾插O(1)
}

由于新链表的节点不是重新 malloc 开辟的新空间，而是直接将原链表中 “值不为 val” 的节点 “拿过来”，通过修改指针指向，将其串联到新链表中。，原链表中值为 val 的节点会被跳过（最终被释放），但新链表的节点完全来自原链表的 “有效节点”。

算法过程中，仅额外定义了新链表的头指针 newHead 和尾指针 newTail 这两个指针变量（用于管理新链表的首尾）。它们的空间是固定的（与 N无关），因此额外空间的复杂度是 O(1)。

由于力扣上的想要调试需要开通会员，这里我直接在VS上手搓一个单链表方便调试 源码如下：

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>

struct ListNode {
	int val;
	struct ListNode* next;
};

typedef struct ListNode ListNode;

struct ListNode* removeElements(struct ListNode* head, int val)
{
	//创建新链表
	ListNode* newHead, * newTail;
	newHead = newTail = NULL;

	ListNode* pcur = head;
	while (pcur)
	{
		//判断pcur节点的值是否为val
		if (pcur->val != val)
		{
			//尾插
			if (newHead == NULL)
			{
				//链表为空
				newHead = newTail = pcur;
			}
			else {
				//链表非空
				newTail->next = pcur;
				newTail = newTail->next;
			}
		}
		pcur = pcur->next;
	}
	return newHead;
}

void test01()
{
	ListNode* node1 = (ListNode*)malloc(sizeof(ListNode));
	ListNode* node2 = (ListNode*)malloc(sizeof(ListNode));
	ListNode* node3 = (ListNode*)malloc(sizeof(ListNode));
	ListNode* node4 = (ListNode*)malloc(sizeof(ListNode));
	ListNode* node5 = (ListNode*)malloc(sizeof(ListNode));
	ListNode* node6 = (ListNode*)malloc(sizeof(ListNode));
	ListNode* node7 = (ListNode*)malloc(sizeof(ListNode));

	node1->val = 1;
	node2->val = 2;
	node3->val = 6;
	node4->val = 3;
	node5->val = 4;
	node6->val = 5;
	node7->val = 6;

	node1->next = node2;
	node2->next = node3;
	node3->next = node4;
	node4->next = node5;
	node5->next = node6;
	node6->next = node7;
	node7->next = NULL;

	ListNode* plist = node1;
	ListNode* newHead = removeElements(plist, 6);
}

int main()
{
	test01();
	return 0;
}

在这里插入图片描述

这里发现程序预想有误差，怎么还有6呀

仅管这里把5这个节点拿下来了，但拿下来的5的next指针并没有发生改变，其next指针依旧指向下一个节点，也就是把5拿下来尾插的时候，6也拿下来了，这里当遍历完链表跳出循环后，将newTail->next指针置为NULL

在这里插入图片描述

在这里插入图片描述

然而发现还是不对，如果链表为空，pcur为空，while循环不进入，newTail为空指针，解引用必定会报错，所以还需加一个链表为空的特殊情况

在这里插入图片描述

这样就没有问题了，一般在算法平台写算法题的时候不用加assert，算法题是通过远程服务器来判题的，加了assert会出现弹窗

二、反转链表

在前面的文章中写过数组的反转

在这里插入图片描述

定义两个下标left和right，反转完成之后left++，right–，当left>=right时跳出循环

但是链表不可以这样，链表是单向的，right无法向左走

思路一：创建新链表，遍历原链表将节点头插到新链表中

在这里插入图片描述

在这里插入图片描述

依次类推

在这里插入图片描述

此方法的时间复杂度为O（1）

在这里插入图片描述

思路2：创建三个指针，改变指针的指向

在这里插入图片描述

只要n2节点不为空，让n2->next不再指向n3，而是指向n1

在这里插入图片描述

此时再让n1走到n2，n2走到n3，n3走到n3的下一个节点

在这里插入图片描述

以此循环往复，到这一步

在这里插入图片描述

此时n3为空，n2不为空，此时让n2->next指向n1，此时n1走到n2，n2走到n3，n3为空，无法继续向下走，n2为空跳出循环，此时新链表的头就是n1指向的节点。

在这里插入图片描述

该方法只改变了指针的指向，既不需要遍历原链表，也不需要头插，可以说是非常方便

在这里插入图片描述

这里报错说对空指针进行解引用了 因为特殊情况当链表为空的时候，n1，n2，n3都为空，n3=n2->next对空指针进行了解引用，所以空链表要特殊处理

在这里插入图片描述

三、链表的中间节点（快慢指针）

在这里插入图片描述

思路1：求链表总长度，总长度/2取整，按数组下标的形式来数，得到的就是中间节点的位置，遍历找中间节点

简单的一个代码样例如下：

while(求链表总长度)
{}
size/2=mid
while(mid)---根据mid找中间位置

可以直观的看出时间复杂度为O（N）

思路2：快慢指针，慢指针每次走一步，快指针每次走两步

在这里插入图片描述

在这里插入图片描述

在链表之中有偶数个节点，有奇数个节点，两个循环判断条件有一个为假就会跳出循环

在这里插入图片描述

这里之所以慢指针走一步，快指针走两步能解决这个问题，原因在于

在这里插入图片描述

快指针最终会把整个链表遍历完，快指针就可以理解为节点的个数，满指针为n/2，也就是链表的一半，此时慢指针一定指向的是链表的中间节点

补充：这里while()循环条件里的顺序也不能换

在这里插入图片描述

这一步就是对空指针进行解引用了，原顺序就会直接短路，不会走到第二个表达式里面

四、合并两个有序链表（哨兵位）

在这里插入图片描述

在之前的文章中，合并两个有效数组，第一个数组给的空间是两个有效数据长度之和

思路：创建新链表，合并两个链表则要进行两个节点的值的比较，谁小谁放前，这里定义两个指针l1，l2去遍历两个链表

在这里插入图片描述

在这里插入图片描述

先认为l1小，把l1这个节点放到新链表中，新链表原来为空，l1既为新链表的头也是新链表的尾，然后l1向后遍历

在这里插入图片描述

再比较，l2小，把l2拿下来，newTail成为新的尾，l2也往后走

在这里插入图片描述

在这里插入图片描述

这里l1，l2再比较，认为l1小，l1拿下来，然后l1向后走

在这里插入图片描述

l1为空不能再比较了，所以循环结束条件就是l1，l2有一个为空，跳出循环

此时l2还有一个节点没有尾插到新链表中，所以跳出循环还要进行判断l1，l2是否为空，如果不为空 那就往新链表里进行尾插

在这里插入图片描述

比较完后，在剩下的节点不仅只有一个的情况下，在顺序表中用的是while，这里用if的原因是下图中4这个节点的next会把5，6一起带过来，这里newTail也没有必要往后走了

在这里插入图片描述

这里已经把所有节点都插入到了新链表的后面，因为要返回的是一个指向该链表的头，只管头不管尾

在这里插入图片描述

在这里插入图片描述

可以发现这里出现了报错，由于l1为空，l2只有一个节点，while循环进不去，newHead=newTail=NULL,直到执行到57行，对空指针进行了解引用，所以需要特殊处理，这里分三种list1为空，list2为空，或者都为空

在这里插入图片描述

但是这串代码有些冗余，还可以优化，比如说上面尾插的部分就写了很多重复的代码，导致这一片代码冗余的根本原因是链表存在为空的情况需要特殊处理，所以最开始创建一个非空链表就可以解决这个问题了

可以选择谁小谁当头，但在创建新链表的时候就需要遍历链表来找到小的那一个，还是很麻烦 这里直接malloc一个非空节点

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

最后newHead应该指向新链表的头，所以应该return newHead-next。远程服务器在程序执行结束之后会自动的释放这块空间，但这是我们在函数内部手动申请的，有借有还，再借不难，所以这里我把要指向的新节点保存后，把newHead手动释放掉

在这里插入图片描述

这里个链表里面，我创建的是一个非空链表，其中像操作系统申请了一个节点，没有对其初始化 在该节点内部没有保存任何一个有效的数据，这个节点我们就将其称之为哨兵位，顾名思义，其是一个站岗放哨的功能，这里是起到一个头节点的功能

这里如果想要把list1和list2判空的代码直接删掉，还需要把newHead->next指针置为空，否则还是会报错

在这里插入图片描述

五、链表的回文结构

在这里插入图片描述

该题目我使用C++来写，在C++中不需要typedef就可以直接使用结构体的名称

回文结构：找到中间位置，将其看为一个镜子，两边对称称为回文结构

在这里插入图片描述

那么如何判断一个数组是不是回文结构呢？

在这里插入图片描述

因为两边相同，根据之前说的反转数组，定义两个变量left和right，分别从左往右和从右往左走，每次比较一对，之后left++，right–进行循环

在这里插入图片描述

当left>right，若不存在不相等的情况，则说其是一个回文数组

由于单链表的单向结构特点，所以该方法不适用

思路1：创建新链表保存原链表所有的节点（循环1），反转新链表（循环2）比较旧链表中的节点的值是否相同（循环3）

在这里插入图片描述

这里虽然是3个循环，但其是并列的，所以时间复杂度为O（n）,也没有额外的申请空间，是创建了两个指针，改变指针指向来完成操作的，满足要求

思路2：该方法带有一点投机的成分，由于题目中说链表的长度小于等于900，所以创建一个数组（大小为900），遍历链表将节点的值依次存储在数组中，若数组为回文结构，则链表为回文结构

在这里插入图片描述

在这里插入图片描述

就不讲解了，一看图就懂了，配合下面代码来看

在这里插入图片描述

因为思路2是一种投机的方法，且牛客房判题力度比较轻，如果在力扣上肯定是不通过的，所以这里就有了终极思路3，符合题目要求

思路3：通过快慢指针找链表中间节点，将中间节点作为新链表的头节点，反转链表，遍历原链表和反转后链表节点的值是是否相等

在这里插入图片描述

图中定义两个指针，开始遍历比较，循环条件为mid不为空，比较两个节点的值，相等往后走

在这里插入图片描述

在这里插入图片描述

再看一个奇数个节点的情况

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

这是符合回文结构，如果如下图

在这里插入图片描述

在这里插入图片描述

这里二者指向节点不相同

总结

好消息，开学了，坏消息，搬老校区了，好破好烂，条件好差，图书馆离餐厅宿舍都好远，差评差评差评！！！