C语言中的数据结构--链表的应用1（2）

前言

上一节我们学习了链表的概念以及链表的实现，那么本节我们就来了解一下链表具体有什么用，可以解决哪些实质性的问题，我们借用习题来加强对链表的理解，那么废话不多说，我们正式进入今天的学习

单链表相关经典算法OJ题1：移除链表元素

https://leetcode.cn/problems/remove-linked-list-elements/description/

题目详情

题解

思路一：

要想解决这个题目，我们首先需要创建一个名为 pcur 的变量，用来遍历整个链表，找到与 val 相等的值，当我们找到了值为 val 的节点，我们不能直接释放掉这个节点，这样会导致后面的数据无法被找到，我们此时还需要定义一个变量 prev ，让 prev 一只指向 pcur 的前一个节点。当我们找到值为 val 的节点，该节点此时被 pcur 指向，我们需要用 pcur->next 来找到它的下一个节点，我们再次创建一个变量 next ，把 pcur->next 存入 next 变量中，并且把这个节点与 prev 所指向的节点连接起来，再释放掉 pcur ，此时就完成了移除链表元素的功能

思路二：

我们重新创建一个链表 newHead 和新链表的尾节点指针 newTail ，我们在原链表中进行遍历，将所有值不为 val 的节点尾插至新链表中去。

我们首先需要创建一个名为 pcur 的变量，用来遍历整个链表，若找到的值不为 val ，则直接尾插到新链表的 newTail 后面去，同时让 newTail 指针向后挪动，而 newHead 指针一直保持不变

假设我们用思路二来解决问题

我们想要完成该函数的功能，首先我们需要往函数中传入两个变量

1.链表的头节点 struct ListNode* head

2. value 的取值 int val

在开始插入的时候我们还需要判断链表当前的情况，到底是为空还是不为空

如果链表为空的话，要将 newHead 和 newTail 都赋予 pcur，此时头节点等于尾节点

如果链表不为空，newTail->next 要等于 pcur 而此时 newTail 变量要等于 newTail->next 

排查

此时我们再来考虑一下特殊情况，若是要移除的数据是链表的尾节点。

我们遍历到原链表的倒数第二个数据的时候，倒数第二个数据的 next 指针指向了尾节点，即使不插入最后一个元素到新链表中，倒数第二个节点仍然可以通过它自身的 next 指针找到原链表的尾节点，此时就会导致代码出现错误，原链表中的尾节点还是被插入到了新链表中去了

那么我们怎么才能在这种情况下不带上最后一个节点呢？

当我们找到并且尾插了倒数第二个节点的时候，我们此时把它的 next 指针赋予空指针 NULL，这样他就找不到原链表的最后一个节点了

此时我们还要考虑到一个问题，因为题目中说了，列表的节点数目可以为0，若链表的节点个数为0时，此时我们就不能把 newTail 中的 next 指针设置为空指针，这样就会造成对空指针进行解引用的问题

那么根据上述的逻辑以及注意事项的规避，我们可以写出代码如下：

typedef struct ListNode ListNode;
 
struct ListNode* removeElements(struct ListNode* head, int val)
{
	//创建一个新链表
	ListNode * newHead, * newTail;
	newHead = newTail = NULL;
 
	//遍历原链表
	ListNode* pcur = head;
	while (pcur)
	{
		//找值不为 val 的节点，然后尾插到新链表中
		if (pcur->val != val)
		{
			//链表为空
			if (newHead == NULL)
			{
				newHead = newTail = pcur;
			}
			//链表不为空
			else
			{
				newTail->next = pcur;
				newTail = newTail->next;
			}
		}
		pcur = pcur->next;
	}
	if (newTail)
	newTail->next = NULL;
	return newHead;
}

我们在Leetcode官网检测一下结果是否正确：

代码成功的解决问题，该题目完成

单链表相关经典算法OJ题2：反转链表

题目详情

题解

思路一：

我们可以创建一个新的链表，我们逐一的遍历原链表，让里面的每一个节点按顺序头插到新链表之中去，当遍历结束后，此时我们拿到的新链表就是反转了以后的链表

思路二：

我们先创建三个变量：分别为 n1 n2 n3。我们先让 n1 指向空指针，让 n2 指向链表的头节点，让 n3 指向 n2 的下一个节点

要完成链表的反转，我们需要按以下步骤操作：

1.先让 n2 的 next 指针不再指向 n3 ，而是让它指向 n1 （n1 初始的情况下为空指针）

2.我们再让 n1 指向 n2 ，让 n3 指向它的下一个节点

3.我们重复以上步骤，让 n2 的 next 指针不再指向 n3 ，而是让它指向 n1

4.一直重复以上步骤，当 n2 和 n3 已经找不到节点了，此时我们可以跳出循环，现在 n1 指向的位置就是反转以后链表的头节点

5.因为原题目说了，链表可以为空，所以我们还需要判断是否为空

此时我们来尝试实现代码：

typedef struct ListNode ListNode;
 
struct ListNode* reverseList(struct ListNode* head)
{
	//判空
	if (head == NULL)
	{
		return head;
	}
	//创建三个指针
	ListNode* n1, * n2, * n3;
	n1 = NULL, n2 = head, n3 = n2->next;
	while (n2)
	{
		n2->next = n1;
		n1 = n2;
		n2 = n3;
		if (n3)
			n3 = n3->next;
	}
	return n1;
}

提醒：最后一次让 n3 = n3->next 的代码不能够执行，因为此时 n3 已经是空指针了，不能对空指针进行解引用，所以我们需要对 n3 加以判断

我们现在在Leetcode的官网运行一下代码：

代码成功的解决问题，该题目完成

单链表相关经典算法OJ题3：链表的中间结点

题目

题解

思路一：

我们可以遍历全链表，定义一个变量 count 用来计算遍历的节点数，当遍历结束后直接返回 （count / 2）节点，则该节点就是链表的中间节点

思路二：（快慢指针）

我们首先分为奇数个和偶数个两种情况

我们先定义两个变量，一个叫做 slow 指针，一个叫做 fast 指针，我们让 slow 指针每次走一步，fast 指针一次走两步，2slow = fast

1.若链表的节点数为奇数个，当 fast->next 指针指向到 NULL 指针时，此时 slow 指针刚好指向链表的中间节点

2.若链表的节点数为偶数个，当 fast 指针指向到 NULL 指针时，此时 slow 指针刚好指向链表的中间节点

有了这个思想以后，我们试着写出代码：

typedef struct ListNode ListNode;
 
struct ListNode* middleNode(struct ListNode* head) 
{
	//创建快慢指针
	ListNode* slow = head;
	ListNode* slow = head;
	while (fast && fast->next)
	{
		slow = slow->next;
		fast = fast->next->next;
	}
	//此时slow刚好指向中间节点
	return slow;
 
}

我们在 Leetcode 的官网运行一下代码，看看结果

代码成功的解决问题，该题目完成

结尾

本节我们了解了链表在题目中的应用，下一节同样给大家细细讲解链表在题目中的应用，帮助大家更好的理解链表，那么本节的内容就到此为止了，谢谢您的浏览！！！