【数据结构】链表专题1

前言 本篇博客通过我们之前的总结的链表，来实现一些算法题，让我们来一起看一下链表在题中的应用吧 ​💓 个人主页：小张同学zkf ⏩ 文章专栏：数据结构 若有问题 评论区见📝 🎉欢迎大家点赞👍收藏⭐文章

1.移除链表元素

这个就是一道经典算法题了

这个题简单来说就是移除指定值的节点

第一个思路也就是我们最容易想到的思路，就是直接遍历一下这个链表，一个个判断是否值与特定值相等，相等的话删去

第二个思路就是创建新链表，找值与指定值不一样的，然后尾插到新链表中

我们把这个思路的代码写一下，我们创建个新链表，while遍历原链表，当找到不是指定值的节点时，我们尾插到我们的新链表中，对了，若刚开始新链表为空时，此刻不用尾插，头结点就是新来的节点

2.反转链表

第一个思路，它不是要反转链表嘛，那我直接创建个新链表，然后遍历原链表，将原链表的节点一个个头插到新链表中，就可以实现反转链表了

第二个思路，比较难想到，但确实很巧妙，三指针法，创建三个指针n1,n2,n3，n1指向空指针，n2指向头结点，n3指向头节点的下一个节点

思路是改变n2节点的指向，让n2节点指向n1,然后，n1=n2,n2=n3,n3等于原n3的下一个节点

最后当n1指向最后一个节点时，结束，此刻链表为反转链表，当n3指向空时，n3就不能再指向它的下一个了，不能对空指针解引用

由于刚开始只有n2指向的是头结点，所以遍历循环的条件就是n2，当n3指向空时，n2再指向为空的n3时，遍历结束，当n3等于空时，不能再更改n3，所以需要if判断，代码如下

3.合并两个有序链表

这道题的思路我们要创建一个新链表，然后俩链表进行遍历比较，将较小的节点放入新链表尾插

这样就存在两种结束情况，要么第一个链表先遍历完，此刻链表2还没有完全插入到链表中，所以这种结束情况将链表2剩余节点尾插到新链表中，要么就是第二个链表先遍历完，此刻将第一个链表剩余的节点，尾插到新链表中

代码如下

我们先用两个指针指向两个链表的头结点，创建新链表头结点与尾结点NewHead,NewTail

这里我们要注意一下，我们的遍历条件是只需要一个链表先走完就暂停遍历，所以此刻while循环里的逻辑关系就是“&&”

我们可以看图上的绿色部分，这里是不是发现代码很一样有点啰嗦，那怎么改才能不判断头结点那，我们可以引入哨兵位——头结点，有哨兵位在就不用在判断头结点了

这样我们就可以把代码优化成

4.链表的中间节点

这道题第一种思路，创建个变量count计数，遍历链表，最后count/2就行

第二种思路，比较难想，用到两个指针，一个是快指针每次走两步，一个慢指针每次走一步，当快指针先指向尾结点时，此刻慢指针指向的就是中间节点的位置，若是偶数，有两个中间节点，此刻返回的也是第二个中间节点

这道题的代码如下

注意看标红的这俩可以交换位置吗

若是偶数个节点，fast最后一次会直接走到空，此刻相当于对fast解引用，空节点解引用肯定报错呀，所以顺序不能变

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

这个题相当经典了！！！

这个问题起源于一个故事

据说著名犹太历史学家Josephus（弗拉维奥·约瑟夫斯）有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决。Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。 17世纪的法国数学家加斯帕在《数目的游戏问题》中讲了这样一个故事：15个教徒和15 个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是教徒。

这个题我们就需要将链表弄成环形链表，让尾结点指向头结点，先打出一个环形链表来

我们接下来找规律我们用双指针法第一个指针pcur指向头结点，prev指针指向上一个节点也就是环形链表的尾结点。

然后我们让pcur指向的第一个节点计数1，然后pcur指针指向第二个节点，prev指向第一个节点，此刻的pcur指向的第二个节点计数2，所以要释放第二个节点，在释放这个节点之前，我们先让上一个节点指向下一个节点避免因释放找不到下一个节点，第一个节点先通过第二个节点指向第三个节点，再释放第二个节点

释放完这个节点就成了图上的样子，接下来继续移动pcur，让pcur指向第三个节点，pcur指向的节点重新计数1,1达成不了销毁的条件，pcur继续下移到第四个节点，prev始终记录pcur上一个节点，prev指向第三个节点，此刻prev指向的节点四计数2，销毁节点四，还是销毁之前先让3指向5，再销毁4

依次类推，最后就只剩下3，此刻pcur指向它自己

代码如下：

6.分割列表

这道题有三种思路

第一个思路：直接在原链表上修改

第二个思路：创建新链表，遍历原链表

第三个思路：创建两个链表，一个链表用来尾插小一点的数，另一个尾插大一点的数，最后俩链表再合并就行。

这个我们要注意在合并大小链表时要让小链表最后一个节点指向大链表的头结点（哨兵位）的下一个节点，再让大链表最后一个节点next值置空，否则会进入死循环 ！！！

结束语 这篇博客主要总结了些链表有关习题，这些习题非常经典，值得我们反复观看 OK，本篇博客结束，谢谢观看！！