devbox
我家小花儿
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【数据结构】单链表经典算法题的巧妙解题思路

作者：我家小花儿 | 2024-05-01 12:06:26

赞

踩

【数据结构】单链表经典算法题的巧妙解题思路

目录

题目

1.移除链表元素

2.反转链表

3.链表的中间节点

4.合并两个有序链表

5.环形链表的约瑟夫问题

解析

题目1：创建新链表

题目2：巧用三个指针

题目3：快慢指针

题目4：哨兵位节点

题目5：环形链表

 

21a985acba5c44d0bd631063c3da57fb.gif

介绍完了单链表，我们这次来说几个经典的题目，本篇的题目衔接下一章双向链表哦~ 

题目

1.移除链表元素

5ff1a09e51584ef6a7b6a7f42a66f4db.png

58f9482b27f94aa986062bacb1953d93.png

 

 

2.反转链表

f5f9d4c1b002450cb11b4ca2a0672adc.png

1c78f9fc6c4b472da5302ba5534c352d.png

 

 

3.链表的中间节点

099e32f128ac43488ae004af12f205ff.png

a0fac974d2114f60b1a18eaa11556b79.png

 

 

4.合并两个有序链表

14c5d0af1acc4ca5a6aa69eb2c6f48eb.png

c99c5146238c403f813d88203a284dc3.png

 

 

5.环形链表的约瑟夫问题

2d20bbd0a403419faf8208c5a66f7b86.png

4e1d24c4ca6f41e1969078cb2dbead51.png

 

a5993e5a565e4f89a80e20cae1290f65.gif

 

我们来看看本篇要介绍的解法吧 

解析

这里介绍的解析仅供参考，算法题的实现思路是很多的，小编就不一一详细介绍了，我们主要介绍小编认为比较好的方法~

题目1：创建新链表

思路：找值不为val的节点，尾插到新链表中

cc2d42c8efcf45ccaac8b2e7f60e5259.png

 pcur不等于val时，就把节点放在新链表中，新链表初始为空链表，所以新链表的第一个节点既是newhead也是newtail，放好后pcur往后走，继续判断节点是否等于val

a8aedbb3066c4bfab75a88439670c09c.png

 pcur所指向的节点不等于val，把这个节点尾插到新链表里面，newhead不变，newtail往后走，pcur也往后走，继续判断

7d935846ae494697826e60989876b5ae.png

 此时pcur指向的节点值为val，pcur再往后走，其余不变

ec12095ab8954860a9d815324a317191.png

一直到pcur遍历完原链表，此时新链表就是去掉所有等于val值的节点的链表

a00a51f4818d4dc3bf98657cd2c6f370.png

 我们代码实现一下

首先把结构体类型 struct ListNode 换个名字，方便定义，就换成ListNode

typedef struct ListNode ListNode;

 然后在题目给的函数中进行实现

  1. typedef struct ListNode ListNode;
  2. struct ListNode* removeElements(struct ListNode* head, int val) 
  3. {
  4. 	ListNode* newhead, * newtail;//定义新头节点、新尾节点
  5. 	newhead = newtail = NULL;//新链表初始时为空
  6. 	ListNode* pcur = head;//pcur初始时指向原链表首节点
  7. 	while ()//开始遍历链表
  8. 	{
  9.  
  10. 	}
  11. }

循环结束的条件应该是pcur不为NULL，循环体里面就是刚刚分析的过程

  1. struct ListNode* removeElements(struct ListNode* head, int val) 
  2. {
  3. 	ListNode* newhead, * newtail;//定义新头节点、新尾节点
  4. 	newhead = newtail = NULL;//新链表初始时为空
  5. 	ListNode* pcur = head;//pcur初始时指向原链表首节点
  6. 	while (pcur)//开始遍历链表
  7. 	{
  8. 		if (pcur->val != val)//找pcur不为val的节点
  9. 		{
  10. 			if (newhead == NULL)//新链表为空
  11. 			{
  12. 				newhead = newtail = pcur;
  13. 			}
  14. 			else//新链表不为空
  15. 			{
  16. 				newtail->next = pcur;
  17. 				newtail = newtail->next;
  18. 			}
  19. 		}
  20. 		pcur = pcur->next;//继续往后遍历
  21. 	}
  22. 	if(newtail)
  23. 	    newtail->next = NULL;
  24.     return newhead;
  25. }

 

 

题目2：巧用三个指针

参考思路1：依旧是新创建一个链表，遍历原链表，将原链表中的节点采用头插的形式放在新链表中，就可以实现链表的翻转

参考思路2：创建3个指针，完成原链表的翻转

我们来实现思路2，这个思路一般不太好想

创建3个变量，n1、n2、n3初始时分别指向NULL、节点1、节点2

d425d1d725ca4d63808139f6075ea591.png

然后让n2指向n1，n1走到n2的位置，n2走到n3的位置，n3走向下一个节点

3812d7a0bd8d4c7b8c1b16403c525856.png

然后再重复上面的步骤，n2指向n1，n1走到n2的位置，n2走到n3的位置，n3走向下一个节点，

2b0bbb746b2a445d8f58968e91a170b6.png

 走到这里的时候n3就不能继续走了，n1和n2继续走

ee6fe9718f714cfc9ad3fb327cc73e92.png

此时n1就是链表的新头节点

我们来代码实现，依旧是重命名一下，把结构体类型 struct ListNode 换个名字，方便定义，换成ListNode

typedef struct ListNode ListNode;

然后在题目给的函数中实现

  1. typedef struct ListNode ListNode;
  2. struct ListNode* reverseList(struct ListNode* head) 
  3. {
  4. 	ListNode* n1, * n2, * n3;//创建3个变量
  5. 	n1 = NULL;//给三个变量赋值
  6. 	n2 = head;
  7. 	n3 = n2->next;
  8. 	while (n2)
  9. 	{
  10. 		n2->next = n1;
  11. 		n1 = n2;
  12. 		n2 = n3;
  13. 		if(n3) //n3为不空时才继续往后走
  14. 			n3 = n3->next;;
  15. 	}
  16. 	return n1;
  17. }

这是链表不为空的情况，那链表为空时呢？直接返回 head 就可以了

  1. typedef struct ListNode ListNode;
  2. struct ListNode* reverseList(struct ListNode* head) 
  3. {
  4. 	if (head == NULL) //空链表
  5. 		return head;
  6. 	//非空链表
  7. 	ListNode* n1, * n2, * n3;//创建3个变量
  8. 	n1 = NULL;//给三个变量赋值
  9. 	n2 = head;
  10. 	n3 = n2->next;
  11. 	while (n2)
  12. 	{
  13. 		n2->next = n1;
  14. 		n1 = n2;
  15. 		n2 = n3;
  16. 		if(n3) //n3为不空时才继续往后走
  17. 			n3 = n3->next;;
  18. 	}
  19. 	return n1;
  20. }

 

 

题目3：快慢指针

这道题的思路也很多，本篇想通过这题介绍一种很妙的方法，快慢指针，快慢指针在之后的很多题中也有很多应用

先来介绍一下快慢指针，slow表示慢指针，fast表示快指针

9f12767696a040719bd8b511acdba67e.png

慢指针slow一次往后走一步，快指针fast一次往后走两步

4f80cc871c9c4b53aab48894faf64c45.png

fast没有走到空，继续走，slow一次往后走一步，fast一次往后走两步

88fb848cceae4d9fa25dc301f4bda3c4.png

fast不能再继续往后走，此时slow所指向的节点就是链表的中间节点，这是节点个数为奇数的情况如果节点个数为偶数个呢？我们来看看

88c576d3c8534260a348193ba307a5ce.png

依旧是慢指针slow一次往后走一步，快指针fast一次往后走两步

d0e6ff8f3dc34d4aae1c7c9167eae83e.png

e6ee7dace5554da58b111e9939e140f4.png

862cd337a5ec40e284b95eba4bd55850.png

此时fast走到空了，不再继续往后走，slow所指向的节点正是第二个中间节点

这就很简单了，我们将快慢指针运用到题目中，代码实现一下

  1. typedef struct ListNode ListNode;
  2. struct ListNode* middleNode(struct ListNode* head) 
  3. {
  4. 	ListNode* slow, * fast;
  5. 	slow = fast = head;
  6. 	while (fast && fast->next)
  7. 	{
  8. 		slow = slow->next;
  9. 		fast = fast->next->next;
  10. 	}
  11. 	return slow;
  12. }

这里需要注意：while循环里面的判断条件 (fast && fast->next) 中 fast 不能和 fast->next 交换位置，因为如果链表结点个数是偶数个时，fast会走到NULL，当fast走到NULL时，while再对fast->next进行判断，此时可以对空指针解引用吗？不可以。所以fast->next不可以放在前面。当fast放在前面，此时fast为NULL，直接退出循环，根本就不会对后面的表达式进行判断，也就不会出现对空指针解引用的情况。

 

 

题目4：哨兵位节点

我们先说没有哨兵位的代码，哨兵位后面再分析

这题我们先选择创建新链表，遍历原链表，我们定义两个指针遍历两个链表

a76017dda471478080ebb6a11a24eb5b.png

把值小的节点放在新链表中，相等的话随便放哪个都行，然后让相应的指针往后走一个f93fbb731a7e420bb8c7e7d5be45a99c.png

此时L1和L2比较，L1比L2小，把L1的节点放到新节点，然后L1往后移

0ea50b1688f54d968c4ff5e7bd74f07d.png

然后再依次向后比较，一直到L1或L2走到NULL为止，遍历结果只有两种情况，要么L1为空，要么L2为空

1aea9e8479fe4ababd240e2512b574ff.png

 我们代码实现一下，先写L1的值小于L2的值的时候

  1. typedef struct ListNode ListNode;
  2. struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
  3. {
  4. 	ListNode* L1 = list1; //遍历原链表
  5. 	ListNode* L2 = list2;
  6. 	ListNode* newhead, * newtail; //创建新链表
  7. 	newhead = newtail = NULL;
  8. 	while (L1 && L2)//循环遍历，有一个走到NULL就退出
  9. 	{
  10. 		if (L1->val < L2->val)//L1的节点值小
  11. 		{
  12. 			if (newhead == NULL) //新链表为空链表
  13. 			{
  14. 				newhead = newtail = L1;
  15. 			}
  16. 			else //新链表不为空链表
  17. 			{
  18. 				newtail->next = L1;//把L1放在新链表
  19. 				newtail = newtail->next;
  20. 			}
  21. 			L1 = L1->next;//L1往后走
  22. 		}
  23. 		else //L2的节点值小
  24. 		{
  25.  
  26. 		}
  27. 	}
  28. }

L2小于L1的时候也是类似的，此时while循环内代码为

  1. 	while (L1 && L2)//循环遍历，有一个走到NULL就退出
  2. 	{
  3. 		if (L1->val < L2->val)//L1的节点值小
  4. 		{
  5. 			if (newhead == NULL) //新链表为空链表
  6. 			{
  7. 				newhead = newtail = L1;
  8. 			}
  9. 			else //新链表不为空链表
  10. 			{
  11. 				newtail->next = L1; //把L1放在新链表
  12. 				newtail = newtail->next;
  13. 			}
  14. 			L1 = L1->next;//L1往后走
  15. 		}
  16. 		else //L2的节点值小
  17. 		{
  18. 			if (newhead == NULL) //新链表为空链表
  19. 			{
  20. 				newhead = newtail = L2;
  21. 			}
  22. 			else //新链表不为空链表
  23. 			{
  24. 				newtail->next = L2;//把L2放在新链表
  25. 				newtail = newtail->next;
  26. 			}
  27. 			L2 = L2->next;//L2往后走
  28. 		}
  29. 	}

跳出循环后有两种情况，要么L1先走到空，要么L2先走到空 ，上面的情况就是L1走到空，L2没有走到空，我们直接把L2拿下来尾插就行了，出while循环后的代码如下

  1.     //跳出循环后
  2.     if (L2) //L2没走到空
  3. 	    newtail->next = L2;
  4.     if (L1) //L1没走到空
  5. 	    newtail->next = L1;
  6. return newhead;

我们还需要处理一下空链表的情况，空链表的情况代码放在函数体最前面

  1. 	//空链表的情况
  2. 	if (list1 == NULL)
  3. 		return list2;
  4. 	if (list2 == NULL)
  5. 		return list1;

 

我们会发现代码重复的部分很多，我们如何去优化它？首先要找为什么会重复

6bd7cc92f5a8418ab7748fb3a21b2428.png

我们向操作系统申请一个空间，这个空间不存有效数据

newhead = newtail = (ListNode*)malloc(sizeof(ListNode));

此时链表也改变了

79d65f76922147ffbc70b8bb7a34e526.png

a2ef885af9cd4332b081269caa100503.png

 所以现在的代码就变了，返回值也变了

  1. typedef struct ListNode ListNode;
  2. struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
  3. {
  4. 	//空链表的情况
  5. 	if (list1 == NULL)
  6. 		return list2;
  7. 	if (list2 == NULL)
  8. 		return list1;
  9. 	ListNode* L1 = list1; //遍历原链表
  10. 	ListNode* L2 = list2;
  11. 	ListNode* newhead, * newtail; //创建新链表
  12. 	newhead = newtail = (ListNode*)malloc(sizeof(ListNode));
  13.  
  14. 	while (L1 && L2)//循环遍历，有一个走到NULL就退出
  15. 	{
  16. 		if (L1->val < L2->val)//L1的节点值小
  17.         {
  18. 	        newtail->next = L1; //把L1放在新链表
  19. 	        newtail = newtail->next;
  20. 	        L1 = L1->next;//L1往后走
  21.         }
  22.         else //L2的节点值小
  23.         {
  24. 	        newtail->next = L2;//把L2放在新链表
  25. 	        newtail = newtail->next;
  26. 	        L2 = L2->next;//L2往后走
  27.         }
  28. 	
  29. 	}
  30. 	//跳出循环后
  31. 	if (L2) //L2没走到空
  32. 		newtail->next = L2;
  33. 	if (L1) //L1没走到空
  34. 		newtail->next = L1;
  35. 	return newhead->next;
  36. }

我们malloc的空间要记得释放，所以可以在return上面加三排代码，而且return的值也要改一下

  1.     ListNode* ret = newhead->next;//存newhead->next的值
  2.     free(newhead);
  3.     newhead = NULL;
  4.     return ret;

所以这里的头节点就是哨兵位

71492255f7e443d0826dc278c5eaede6.png

 

题目5：环形链表

我们先介绍一下约瑟夫问题的历史背景

据说著名犹太 历史学家 Josephus（ 弗拉维奥·约瑟夫斯 ）有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。约瑟夫将自己和他的朋友安排在16和31个位置，于是逃脱了这场死亡游戏

来看一下环形链表

42aa0b6cca164ea1a96909ed0dd1855d.png

我们画个图简单介绍一下

56d9eab6586b4025953f803d94dd1fe3.png

此时把3节点去掉，继续从下一个存在的节点开始报数

969f34842edc439b9da4641eb78b2b85.png

再把节点1去掉，继续从下一个存在的节点开始报数

9d7763c77b2849b6b462f1fcdc1fd160.png

把节点5去掉，现在留下两个节点，如果约瑟夫和他的朋友想要存活，就要站在2或4的位置

5cf9d7b8879a403280434d80cbde3bfb.png

 

那么这道题就是类似，不过是留下一个节点

拿5个节点，报数为2举例

f1c808c0c19946248ebfce25cd189739.png

 53166b1ec5f04593b51b926faba375e6.png

714b527292c249af83c0768a54cb69d8.png

最后就留下了节点3

代码中我们如何分析呢？看下图。

fc878fd6feb4455199293fac45466498.png

数1之后数2，此时pcur后移，prev后移

464d0a535033455f92470a5e322876f6.png

pcur所指向的节点数到了2，要销毁pcur所指的节点，销毁的时候先让prev的next指针指向pcur的next

61712a82f8784b7aaffb9df910a2f6aa.png

然后把pcur指向的节点销毁，并且让pcur指向下一个节点，也就是prev的next指针指向的位置

ae38073a76f941c7b86f2ca7c19d7e32.png

然后继续数数，从1开始

0c5e5080dd7840d68eeb965487ec677a.png

2e4121bf699d43b7a40b9d83c61e9e5e.png

然后就是重复步骤，当只剩下两个节点时，分析一下

b6b75f1cf1774f968a36d53d3dad6617.png

pcur报数为2，删掉5这个节点，要先让prev的next指针指向pcur的next，也就是节点3此时自己指向自己

4d13466df44e4f7690cc214e03163691.png

然后再销毁节点5，此时pcur也指向节点3 

4c25a89e346c47a89a440a62b8c100c1.png大概分析就是这样，我们代码实现一下

先写一个创建节点的函数

  1.  typedef struct ListNode ListNode;
  2.  ListNode* BuyNode(int x)//创建节点
  3.  {
  4.     ListNode* node=(ListNode*)malloc(sizeof(ListNode));
  5.     if(node==NULL)
  6.     {
  7.         exit(1);
  8.     }
  9.     node->val = x;
  10.     node->next = NULL;
  11.     return node;
  12.  }

然后写带环链表的函数

  1.  ListNode* CreatCircle(int n)//创建带环链表
  2.  {
  3.     ListNode* phead=BuyNode(1);//先创建头节点
  4.     ListNode* ptail=phead;
  5.     for (int i = 2; i <= n; i++)
  6.     {
  7.         ptail->next=BuyNode(i);//尾插新节点
  8.         ptail = ptail->next;
  9.     }
  10.     ptail->next=phead;//头尾相连，变成循环链表
  11.     return ptail;
  12.  }

然后在ysf函数中实现

  1. int ysf(int n, int m )
  2. {
  3.    ListNode* prev = CreatCircle(n);//环形链表尾节点由prev接收
  4.    ListNode* pcur = prev->next;//头节点由pcur接收
  5.    int count = 1;
  6.    while (pcur->next != pcur)
  7.    {
  8.       if(count == m) //需要销毁节点
  9.       {
  10.         prev->next = pcur->next;
  11.         free(pcur);
  12.         pcur = prev->next;
  13.         count = 1;//重新计数
  14.       }
  15.       else //不用销毁节点
  16.       {
  17.         prev = pcur;
  18.         pcur = pcur->next;
  19.         count++;
  20.       }
  21.    }
  22.     return pcur->val;
  23. }

 

 这次分享就到这里了，拜拜~

e7b175756e8644dea610a7ec209820f5.gif

 

 

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家小花儿/article/detail/518767
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号