【数据结构】_单链表_相关面试题（一）

🎉🎉🎉

hello 朋友们！今天我们将对单链表的相关面试题进行详细的讲解！

🖋️🖋️🖋️

下面就开始吧~GO!

1.移除链表指定元素

题目：

思路原理：
这里我们要用双指针来完成，前一个指针指向外面（头指针前面），后一个指针指向头位置，若没有找到指定元素，那么就先将前指针指向后一个指针位置，后指针在往后找；若找到指定元素，先保存后指针指向的下一个节点的地址，然后释放掉指定元素，再将前一个指针指向的next指向刚刚保存的地址；

代码分析：

//删除指定元素
void removeElements(SListNode**pphead,int x)
{
	//定义两个指针 前驱指针+头指针
	SListNode* prev = NULL;
	SListNode* cur = *pphead;
	while (cur)
	{
		//找到指定元素x
		if (cur->val == x)
		{
			SListNode* next = cur->next;
			//头删
			//判断是不是头删位置(是）
			if (prev == NULL)
			{
				//先拿到下一个节点的地址
				
				free(cur);
				cur = next;
				*pphead = cur;
			}
			//普通删
			else
			{
				free(cur);
				prev->next = next;
				cur = next;
			}

		}
		//没有找到指定元素
		else
		{
			prev = cur;//prev先走到cur的位置
			cur = cur->next;//cur在往后走一个位置
		}
	}
}
test1()
{
    //创建单独的节点
	SListNode* n1 = Great_SListNode(1);
	SListNode* n2 = Great_SListNode(2);
	SListNode* n3 = Great_SListNode(6);
	SListNode* n4 = Great_SListNode(3);
	SListNode* n5 = Great_SListNode(4);
	SListNode* n6 = Great_SListNode(5);
	SListNode* n7 = Great_SListNode(6);
	//将每个节点相连形成单链表
	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = n5;
	n5->next = n6;
	n6->next = n7;
	SLPrint(n1);
	//删除指定元素6
	removeElements(&n1, 6);
	SLPrint(n1);
}
int main()
{
	test1();
}

详细解析：

1. 初始化指针
   prev：前驱指针，初始化为 NULL，用于记录当前节点 cur 的前一个节点。
   cur：当前指针，初始化为链表的头节点。

2. 处理头删情况
   当prev为NULL时，说明当前要删除的节点是头节点。
   首先保存cur的下一个节点的地址到next中。
   然后释放cur所指向的节点。
   接着将cur指向 next，更新cur的位置。
   最后更新头指针*pphead为 cur。

3. 处理普通删除情况
   当prev不为NULL时，说明当前要删除的节点不是头节点。
   同样先保存cur 的下一个节点的地址到next中。
   释放cur所指向的节点。
   将prev的next指针指向 next，跳过cur节点。
   最后将cur指向 next，更新cur的位置。

注意：
使用双重指针是因为在删除头节点时，需要修改头指针的值。
removeElements 函数通过*pphead可以修改实际的头指针，保证在删除头节点时，链表的头指针能被正确更新

运行结果：

2.反转一个单链表

题目：

代码分析：

SListNode* ReverseSList(SListNode* phead)
{
	//定义三个指针
	SListNode* n1 = NULL;
	SListNode* n2 = phead;
	SListNode* n3 = n2->next;
	while (n2)
	{
		//反转n2的指向
		n2->next = n1;
		n1 = n2;
		n2 = n3;
		if (n3)//n3本身不为空的情况
		{
			n3 = n3->next;
		}
	}
	return n1;
}
test1()
{
	SListNode* n1 = Great_SListNode(1);
	SListNode* n2 = Great_SListNode(2);
	SListNode* n3 = Great_SListNode(6);
	SListNode* n4 = Great_SListNode(3);
	SListNode* n5 = Great_SListNode(4);
	SListNode* n6 = Great_SListNode(5);
	SListNode* n7 = Great_SListNode(6);
	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = n5;
	n5->next = n6;
	n6->next = n7;
	SLPrint(n1);
	//删除指定元素6
	//removeElements(&n1, 6);

	SListNode*phead=ReverseSList(n1);
	SLPrint(phead);

}
int main()
{
	test1();
}

详细解析：

1. 指针初始化
   n1：初始化为 NULL，用于记录反转后链表的新头节点。
   n2：初始化为原链表的头节点 phead，用于遍历原链表。
   n3：初始化为n2的下一个节点，如果n2为空，则n3为 NULL。

2. 循环反转
   在while循环中，每次将n2的next指针指向 n1，实现节点的反转。
   然后将n1移动到n2的位置，n2 移动到n3的位置。
   如果n3不为空，则将n3移动到下一个节点。
   注意：当 n2 为空时，循环结束，此时 n1 指向反转后链表的头节点，将其返回。

3. if (n3) 判断的必要性
   在链表反转过程中，当n2指向链表的最后一个节点时，n3 会是 NULL。如果没有if (n3)这个判断，直接执行 n3 = n3->next; 会尝试访问NULL指针的next成员，这会导致空指针异常，程序崩溃。

运行结果：

3.链表的中间节点

题目：

代码分析：

//中间节点
SListNode* middleNode(SListNode*phead)
{
	//定义两个指针 快+慢指针
	SListNode* slow = phead;
	SListNode* fast = phead;
	while (fast && fast->next)//注意这里顺序不可以颠倒,因为当fast为空时，NULL->next是未定义行为（报错）
	{
		fast = fast->next->next;//快指针走两步
		slow = slow->next;//慢指针走一步

	}
	return slow;//找到中间节点
}
test1()
{
	SListNode* n1 = Great_SListNode(1);
	SListNode* n2 = Great_SListNode(2);
	SListNode* n3 = Great_SListNode(6);
	SListNode* n4 = Great_SListNode(3);
	SListNode* n5 = Great_SListNode(4);
	SListNode* n6 = Great_SListNode(5);
	SListNode* n7 = Great_SListNode(6);
	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = n5;
	n5->next = n6;
	n6->next = n7;
	SLPrint(n1);//调用 SLPrint 函数来打印以 n1 为头节点的单链表的所有节点的值。
	SListNode* MiddleNode = middleNode(n1);
	printf("%p: %d\n", MiddleNode, MiddleNode->val);

}
int main()
{
	test1();
}

详细解析：

当快指针 fast 到达链表末尾（fast 为空或 fast->next 为空）时，慢指针 slow 正好指向链表的中间节点，将其返回。
注意：当链表长度为偶数时，快指针最终会走到 NULL，此时慢指针正好位于第二个中间节点。

问题：为什么 slow 最终指向 3？

• 循环终止条件：当 fast 指向节点 4 时，执行第三次循环：

• 检查条件：fast 指向 4（非空），fast->next 指向 5（非空），条件成立。

• 移动快指针：fast = fast->next->next = 5->next = NULL。

• 移动慢指针：slow = slow->next = 6->next = 3。

• 再次检查条件：fast 为 NULL，退出循环。

运行结果：

4.返回倒数第k个节点

题目:

本题思路：
定义两个快慢指针，因为要找倒数第k个节点，所以先将快指针走k步，然后在慢指针走一步，快指针再走一步。（简单理解一下就是假设两个人跑步，一共100m，要找到50m的地方，找50就先要快的跑50，然后再一起同速跑，当快的跑完了，慢的所在的地方就是要找的50m处）

代码分析：

//找到数第k个节点
SListNode* K_Node(SListNode* phead,int k)
{
	//先拷贝这个k
	int copy_k = k;
	SListNode* slow = phead;
	SListNode* fast = phead;
	//先让快指针走K步
	while (copy_k--)
	{
		//fast不为空的情况
		if (fast)
		{
			fast = fast->next;
		}
		//为空 也就是找不到倒数第k个 超过了范围
		else
		{
			printf("没有找到第倒数%d个节点！！！\n", k);
			return NULL;
		}
	}
	//有这个节点
	while (fast)
	{
		fast = fast->next;
		slow = slow->next;
	}
	return slow;//返回这个慢指针节点地址
}
test1()
{
	SListNode* n1 = Great_SListNode(1);
	SListNode* n2 = Great_SListNode(2);
	SListNode* n3 = Great_SListNode(6);
	SListNode* n4 = Great_SListNode(3);
	SListNode* n5 = Great_SListNode(4);
	SListNode* n6 = Great_SListNode(5);
	SListNode* n7 = Great_SListNode(6);
	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = n5;
	n5->next = n6;
	n6->next = n7;
	SLPrint(n1);//调用 SLPrint 函数来打印以 n1 为头节点的单链表的所有节点的值。
	SListNode* k_node = K_Node(n1, 100);
	if (k_node)
	{
		printf("%d", k_node->val);
	}

}
int main()
{
	test1();
}

详细解析：

• copy_k 保存参数k的值，用于控制快指针移动步数，以免改变k的值
• 🤔🤔🤔问题：这里最后打印时为什么要if条件判断???
• • 空指针风险：当k超过链表长度时，K_Node 返回 NULL。若直接访问 k_node->val，会发生空指针解引用，导致程序崩溃（未定义行为）。
• • 安全校验：if (k_node) 用于判断k_node是否为有效节点指针。仅当k_node非NULL时，才访问其成员 val，避免程序因空指针操作崩溃。所以为空时就不访问这个打印，用的是上面else里面的打印。

运行结果：

1. 没有超过范围的

2. 超过范围，找不到k的

5.合并两个有序链表

题目：

代码分析：

//合并两个升序链表
SListNode* mergeTwoLists(SListNode* phead_a, SListNode* phead_b)
{
	SListNode* phead = NULL;//合并链表头节点
	SListNode* ptail = NULL;//合并链表尾节点
	//当链表 A 和 B 都未遍历完时，继续比较当前节点值。
	while (phead_a && phead_b)
	{
		// 将 phead_a 的当前节点加入新链表
		if (phead_a->val <= phead_b->val)
		{
			//若合并链表为空（phead == NULL），新节点即为头节点
			if (phead == NULL)
			{
				phead = ptail = phead_a;// 新链表为空时的初始化
			}
			//否则，通过ptail->next连接新节点，并更新ptail为新节点。
			else
			{
				ptail->next = phead_a; // 链接到尾部
				ptail = ptail->next; // 更新尾部指针
			}
			phead_a = phead_a->next;// 移动原链表指针
			ptail->next = NULL;  // 断开当前节点的后续链接
			//注意这两串代码不可以颠倒
		}
		//同理处理 phead_b
		else
		{
			if (phead == NULL)
			{
				phead = ptail = phead_b;
			}
			else
			{
				ptail->next = phead_b;
				ptail = ptail->next;
			}
			phead_b = phead_b->next;
			ptail->next = NULL;//注意这两串代码不可以颠倒
		}
	}
	//phead_b走完了 处理剩余链表
	if (phead_a)
	{
		ptail->next = phead_a;// 将剩余链表直接接入尾部
	}
	//phead_a走完了
	if (phead_b)
	{
		ptail->next = phead_b;
	}
	return phead;
}

void test2()
{
	SListNode* n1 = Great_SListNode(1);
	SListNode* n2 = Great_SListNode(2);
	SListNode* n3 = Great_SListNode(2);
	SListNode* n4 = Great_SListNode(1);
	SListNode* n5 = Great_SListNode(3);
	SListNode* n6 = Great_SListNode(4);
	SListNode* n7 = Great_SListNode(6);
	n1->next = n2;
	n2->next = n3;
	
	n4->next = n5;
	n5->next = n6;
	n6->next = n7;
	SListNode* phead = mergeTwoLists(n1, n4);
	SLPrint(phead);
}
int main()
{
	test2();
}

详细解析：

1. 参数
   phead_a：链表A的头指针。
   phead_b：链表B的头指针。
   phead：指向合并链表的头节点。
   ptail：指向合并链表的尾节点。
2. 画图

初始：
A: [1] → [2] → [2] → NULL
B: [1] → [3] → [4] → [6] → NULL
phead = NULL, ptail = NULL

步骤1后：
A: [2] → [2] → NULL
B: [1] → [3] → [4] → [6] → NULL
合并链表: [1] → NULL
phead = 1, ptail = 1

步骤2后：
A: [2] → [2] → NULL
B: [3] → [4] → [6] → NULL
合并链表: [1] → [1] → NULL
phead = 1, ptail = 1

步骤3后：
A: [2] → NULL
B: [3] → [4] → [6] → NULL
合并链表: [1] → [1] → [2] → NULL
phead = 1, ptail = 2

步骤4后：
A: NULL
B: [3] → [4] → [6] → NULL
合并链表: [1] → [1] → [2] → [2] → NULL
phead = 1, ptail = 2

步骤5后：
合并链表: [1] → [1] → [2] → [2] → [3] → [4] → [6] → NULL

3. 问题：为什么这两串代码不可以颠倒？

   phead_a = phead_a->next;// 移动原链表指针
   ptail->next = NULL;  // 断开当前节点的后续链接
   

原因：如果颠倒顺序，当处理完一个节点后，原链表指针会提前丢失后续节点的访问路径，导致合并后的链表不完整。

举例说明：

运行结果：

6.链表分割

题目：

原理：

将小于等于x的结点排成一个链表；将大于x的数排成一个链表，然后把这两个链表连接起来

代码分析：

//分割链表
void Partition_Node(SListNode**phead,int x)
{
    //哨兵节点初始化
	SListNode* lesshead, *lesstail;
	SListNode* greaterhead, *greatertail;
	//开辟哨兵位
	lesshead = lesstail = Great_SListNode(-1);//存放小于等于x的链表
	greaterhead = greatertail = Great_SListNode(-1);//存放大于x的链表
	//遍历链表
	SListNode* cur = *phead;//原链表头指针
	while (cur)
	{
		if (cur->val <= x)
		{
			lesstail->next = cur;
			lesstail = lesstail->next;
			cur = cur->next;
			lesstail->next = NULL;
		}
		else
		{
			greatertail->next = cur;
			greatertail = greatertail->next;
			cur = cur->next;
			greatertail->next = NULL;
		}
	}
	SListNode* next = greaterhead->next;
	lesstail->next = next;
	*phead = lesshead->next;
	free(lesshead);//释放哨兵节点内存
	free(greaterhead);//free掉哨兵头
}

void test2()
{
	SListNode* n1 = Great_SListNode(1);
	SListNode* n2 = Great_SListNode(2);
	SListNode* n3 = Great_SListNode(2);
	SListNode* n4 = Great_SListNode(1);
	SListNode* n5 = Great_SListNode(3);
	SListNode* n6 = Great_SListNode(4);
	SListNode* n7 = Great_SListNode(6);
	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = n5;
	n5->next = n6;
	n6->next = n7;
	Partition_Node(&n1, 3);
	SLPrint(n1);
}
int main()
{
	test2();
}

详细解析：

1. 哨兵节点：
   简化链表操作，避免处理头节点为空的边界情况。
   lesshead 和greaterhead分别作为两个子链表的虚拟头节点。
   每个哨兵节点的val设为 -1（无关紧要，仅占位）。
   lesstail 和greatertail初始化为哨兵节点，用于尾插操作。
2. 双链表构建：
   less 链表：存储所有小于等于 x 的节点。
   greater 链表：存储所有大于 x 的节点。
3. 合并两个子链表
   将greater链表的头节点（跳过哨兵）连接到less链表的尾部。
   更新原链表的头指针为less链表的头节点（跳过哨兵）。

画图说明：

❗❗❗注意：

greatertail->next = NULL;
greatertail->next = NULL;
🤔🤔🤔为什么这两个要置空？？？

在遍历原链表并把节点插入到lesshead或greaterhead链表时，每个节点都可能原本连着原链表中的下一个节点。若不把新插入节点的next指针设为 NULL，就会致使新链表中的尾节点依旧指向原链表中的某个节点，这样会造成链表结构混乱，甚至可能产生循环链表。

运行结果：

7.链表的回文结构

题目：

代码分析：

//反转链表
SListNode* ReverseSList(SListNode* phead)
{
	//定义三个指针
	SListNode* n1 = NULL;
	SListNode* n2 = phead;
	SListNode* n3 = n2->next;
	while (n2)
	{
		//反转n2的指向
		n2->next = n1;
		n1 = n2;
		n2 = n3;
		if (n3)//n3本身不为空的情况
		{
			n3 = n3->next;
		}
	}
	return n1;
}
//判断是不是回文结构
int PalindromeList(SListNode* phead)
{
	if (phead == NULL || phead->next == NULL)// 空链表或只有一个节点，是回文结构
	{
		printf("是回文结构\n");
		return 1;
	}
	//定义两个快慢指针
	SListNode* slow = phead;
	SListNode* fast = phead;
	SListNode* prev = NULL;
	//不为空，找到中间节点
	while (fast && fast->next)
	{
		prev = slow;//prev始终指向slow的前一个结点
		slow = slow->next;//慢指针走一步
		fast = fast->next->next;//快指针走两步
	}
	//将中间结点前一链表与后一链表断开
	prev->next = NULL;

	//将中间结点后面的链表反转
	slow = ReverseSList(slow);//调用上面的反转
	
	while (phead)
	{
		if (phead->val != slow->val)
		{
			printf("不是回文结构\n");
			return 0;
		}
		//相等
		else
		{
			phead = phead->next;
			slow = slow->next;
		}
	}
	printf("是回文结构\n");
	return 1;
}

void test3()
{
	SListNode* n1 = Great_SListNode(1);
	SListNode* n2 = Great_SListNode(2);
	SListNode* n3 = Great_SListNode(3);
	SListNode* n4 = Great_SListNode(4);
	SListNode* n5 = Great_SListNode(3);
	SListNode* n6 = Great_SListNode(2);
	SListNode* n7 = Great_SListNode(1);
	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = n5;
	n5->next = n6;
	n6->next = n7;
	SLPrint(n1);
	PalindromeList(n1);

}
int main()
{
	test3();
}

实现思路：

• 找中间节点：使用快慢指针法，快指针fast每次移动两步，慢指针slow每次移动一步，当快指针到达链表末尾时，慢指针正好指向链表的中间节点。同时，使用prev指针记录慢指针的前一个节点。
• 断开链表：将链表从中间节点处断开，分为前半部分和后半部分。
• 反转后半部分链表：调用ReverseSList函数反转后半部分链表。
• 比较前后两部分：同时遍历前半部分链表和反转后的后半部分链表，比较对应节点的值。如果所有节点的值都相等，则链表是回文结构；否则，不是回文结构。

画图解析：

❗❗❗注意：
slow = ReverseSList(slow); 的含义

slow = ReverseSList(slow); 这行代码会调用 ReverseSList 函数对 slow 指针所指向的链表部分进行反转。反转之后，ReverseSList 函数会返回反转后链表的头节点，并且把这个头节点赋值给 slow 指针。

运行结果：

🎇🎇🎇
在这里本章我们就先告一段落啦~

友友们~
我们下期再见噢~