链表经典算法（+OJ刷题）

文章目录

• 前言
• 一、移除链表元素
• 二、链表的中间节点
• 三.反转链表
• 四.合并两个有序链表
• 五.分割链表
• 六.环形链表的约瑟夫问题
• 总结

创作不易，点赞收藏一下呗！！！

---

前言

在上一节，我们介绍了单链表的增，删，查，改接口的实现思路。今天我们就实战运用这些思想来解决一些算法题

一、移除链表元素

链接放在这里：

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

思路一：遍历原链表，遇到满足val==val的节点就删除 

思路非常简单，但是要注意一些细节。

头节点val==val的情况需要特殊考虑，此时就是头删。还有一种特殊情况就是链表为空时直接返回head即可！！！ 

思路二：创建新链表，遍历原链表并将val！=val的节点赋值给新链表

 

注意： 最后一定要判断新链表的尾节点是否指向NULL，如果不是则需要手动置为NULL！！！

思路三：哨兵节点的方式来创建带头新链表，其余思路和二相同

带头链表的好处是尾插时不需要判断新链表是否为空来分情况考虑！！！ 

二.链表的中间节点

链接：

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

思路一：先遍历原链表统计节点个数，再循环来找到中间节点

思路二：快慢指针法 

整体思路 ：定义两个指针来遍历原链表，快指针一次走两步，慢指针一次走一步，当快指针为NULL或快指针的next指针为空时，此时慢指针就正好在中间节点上！！！

注意：循环条件的顺序两个不能写反，否则pfast为空时会报错！！！

三.反转链表

链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

思路一：创建新链表，遍历原链表，进行头插

这个思路比较简单实现，不多赘述！！！

思路二：原地翻转，三指针法 

接下来：

循环进行上述操作，直至pcur为NULL时停止，这样就完成了对链表的反转。 

代码实现如下：

特别注意：一定要单独处理空链表的情况！！！ 

四.合并两个有序链表

链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

思路一：遍历l1链表，在l1链表的基础上将l2链表中的节点插入到特点位置 

这个思路实现的代码可能有些多，我们这里就不重点介绍！！！

思路二：创建新链表

思路三：创建带哨兵节点的新链表 

整体思路和第一题的思路三相仿，感兴趣的友友们可以去看看！！！

我这里就不专门写一份了。

五. 分割链表

链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

 

思路：创建两个带头链表，一个用来存放小于val的节点，另一个存放大于等于val的节点，最后将这两个节点首尾相连 

注意：最后一定要将大礼链表的尾节点的next置为NULL，否则会成环，死循环！！！ 

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

链接：环形链表的约瑟夫问题_牛客题霸_牛客网

思路：运用循环链表

总结： 

我们不能只会做这道题，而是应该掌握这道题目背后的算法思维！！！