【数据结构与算法】8道链表面试真题超详剖析，带你领略算法思想【附思路、动图、源码】_链表经典算法题

?? 前情提要??

本章节是数据结构的链表的相关基础题目讲解~

以下的内容一定会让你对链表相关知识的题目,有一个颠覆性的认识哦！！！

以下内容以C语言的方式实现

以下内容干货满满，跟上步伐吧~

---

作者介绍：

?? 作者： 热爱编程不起眼的小人物??
??作者的Gitee：代码仓库
??系列文章&专栏推荐： 《刷题特辑》、 《C语言学习专栏》、《数据结构_初阶》

??我和大家一样都是初次踏入这个美妙的“元”宇宙?? 希望在输出知识的同时，也能与大家共同进步、无限进步??

---

??导航小助手??

• ??前情提要
• ??面试真题【全面深度解析】
• • ??? 移除链表元素【难度：简单】
  • ??? 反转链表【难度：简单】
  • ??? 链表的中间结点【难度：简单】
  • ??? 链表中倒数第k个结点【难度：简单】
  • ??? 合并两个有序链表【难度：简单】
  • ??? 分割链表【难度：简单】
  • ??? 回文链表【难度：简单】
  • ??? 相交链表【难度：简单】
• ??总结

---

??前情提要

• 大家可以跟着本文的题目讲解进行链表相关知识的复习&加深

  • 若大家对链表还不太熟悉or需要回顾一下基本知识，可点击单链表、带头+双向+循环链表至相关文章进行回顾

• 也欢迎大家上手测试一波??

---

??面试真题【全面深度解析】

?? 移除链表元素【难度：简单】

??题目传送门：

Leetcode：203. 移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val的节点，并返回新的头节点

• 示例 1：

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
1
2

• 示例 2：

  输入：head = [], val = 1
  输出：[]

• 示例 3：

  输入：head = [7,7,7,7], val = 7
  输出：[]

??解题关键：

• 我们只需要遍历链表，一一比较结点的val是否为要删除的

  • 1若为要删除的结点：先释放掉此结点，再将此结点的上一结点链接到此结点的下一结点

  • 2否则，继续遍历比较

特别注意：

• 因为单链表只有后驱指针，无法像带头+双向+循环链表轻易地直接访问某个结点的上一结点

• 所以遍历的时候需要同时安排前（prev）后（cur）指针，去记录上个结点和当前结点的位置

??特殊情况：

• 1如果第一个结点就是要删除的结点val：这种情况下我们需要连头指针head 一起改变挪动

• 2如果整个链表全是要删除的结点val，则也同样连头指针head一起挪动

动图示例：

??实现：

struct ListNode* removeElements(struct ListNode*head, int val)
{
	struct ListNode* cur = head;
	struct ListNode* prev = NULL;
	
	//边走边删除 
	//直至cur走到NULL就停止
	while (cur) 
	{
		//要删除结点时：
		if (cur->val == val)
		{
		
			struct ListNode* next = cur->next;

			//说明要删的是 第一个结点
			if (prev == NULL) 
			{
				free(cur);
				head = next;
				cur = next;
			}
			else
			{
				free(cur);
				prev->next = next;
				cur = next;
			}
		}
		//不需要删除结点时：
		else
		{
			prev = cur;
			cur = cur->next;
		}
	}
	return head;  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

补充：

• 这里设计得也很巧妙，用cur来当循环的结束标志，当链表整体为NULL的时候，cur