当前位置：首页 > ai >正文

刷题记录（5）链表相关操作

ai 2025/8/20 17:44:51

一、链表元素的移除

题目要求很简洁，批量删去链表元素里为val的结点，返回删除结点后的链表的头指针。

很容易想到用我们写过的Find函数，再用我们的删除函数，Find函数免不了对链表元素的遍历，删除函数也免不了遍历，前者是因为必须遍历去对比，后者因为删除函数删除某结点必须知道前一个结点，那就也免不了去遍历。

这个思路按照一般的话就给两层嵌套呗，外层遍历，如果相等就是找到了，那就进入内层去删除，这样的话时间复杂度就是O（N^2），或者空间换时间，一个循环去查找链表中所有值为val的结点，记录下来，再逐个删去，但是这样还是免不了每一个结点都得调用一次删除函数，有点屎山代码的感觉，代码量会非常大。

所以我们不去想这么麻烦的事，对于跟数据结构有关的算法题，我们应当从该题的数据结构的本质去入手。

我们可以用三个指针来遍历，一个是新的头指针newhead，一个是新的尾指针newtail，一个是在原链表进行遍历的pcur，newhead是为了返回值作准备，newtail为下次尾插做准备，pcur是为了遍历完整个链表，思路说完，实践开始：

做题它给的样例有的是需要防御的，比如他万一给的空链表，你下面还怎么解引用：

如果原链表最后一个结点恰好为val的话，我们看似不将其变为尾，但是由于上一个被复制，且next指针扔指向，就会造成多一个的风险：

如果尾结点不置空，那就刚好多了一个结点，且尾结点置空，要保证尾结点存在，这个时候验链表是否为空即可。

说几个指针没啥用，重点在于对链表结构的了解。

二、反转链表

1.暴力头插

容易想到的就是遍历整个链表，一个一个结点拿过来头插。

刚开始我们想象的新链表为空，就先置空,phead是新链表的指针，所以为了方便遍历原链表，那再来一个pcur，用这个指针去遍历。

第一个插入的结点肯定就是新链表的尾结点了，所以要给他的next指针置空，但是应该先后移pcur，不然你置空以后，pcur就不能顺着找到下一个链表结点了。

然后如果新链表不是空的话想想该怎么去改结点指向：

理想状态下头插一个结点应该是这样的效果，但是通过pcur根本不能找到原链表中这个结点的前一个结点，因此还得写一个指针去存pcur前的那个位置：

然后想想我们现在有的操作是什么，方便下一步的改指针方向的先后顺序：

一写出来就发现出事了，真这么干的话，phead = pcur倒是没啥，新头就是pcur，没啥好说的。我们创造出来prev就是为了实现指针方向的转弯，那prev = pcur肯定是用过了，也就是phead ->next = prev才能后移为下次做准备，但是明显pcur没法往后走了，因为phead那一步给它修改了，但是如果：

prev跳过了2这个结点了，如图中所示，既然这样，干脆再来一个pnext。

这次再来看头插还会不会出问题：

好像没啥毛病了。

由于新加了俩指针，检查条件，其实很明显的一点就是pnext肯定先到空，如果pnext到空，pnext = pnext ->next就有问题了：

对于这个样例就是到这种情况了，这样的话，前面都没啥毛病，就是最后一句不行，那干脆这样：

因为新插指针，所以看看初识新链表为空时的操作：

pnext的三目操作符避免原链表只有一个元素，pcur = pcur ->next就为NULL，后对空指针的解引用。

但是这个方法自己写起来废了老鼻子劲了，而且用的指针越多越危险，我们之前做题，双指针都胆战心惊的，就是做的合并两个有序数组。

所以这个方法说好听点是秀肌肉，说不好听点就是没本事。

2.真正来反转

虽然最后题是做出来了，但是实在是颇为艰难，一步一步修改过来的，在这种情况下，我们就会妄求更简单的解法，稍微做了几道用算法的题，印象比较深刻有一个轮转数组的题，不用空间换时间就是原地来对数组进行操作，因此我们现在想优化算法，不如想想怎么原地实现（虽然链表过程中并没有产生过多内存，因为链表节点是有的，额外申请的也就是那四个指针）。

不再拿下来组装，而是换方向：

可以实现吗，大概想一想，最开始得：

假如说这次我们要改结点2的箭头，应该做的就是让它的next为1这个结点，看来还得存下来1这个结点，而且一旦改，还得保存下来原链表下一个结点，方便下次修改，所以等于到头来还是三个指针：

初始化已经很明显了：

有了头插的经验，我们解引用前先验是否为空指针。

大概看一下循环的条件：

p2是我们每次修改方向的结点，p1是需要指向的方向，p3是为了下一个结点的修改而准备，即我们这个思路就是改指针方向嘛，最开始肯定是从第一个结点开始，这个结点的next指针一旦改，那后面的都改不了了，所以再写一个指针存原链表下一个结点，再根据我们写单链表函数时候，找到pos结点前一个结点实际上非常麻烦，干脆再写一个存，初始值为NULL。而跳出循环的条件就应该是p2 == NULL:

返回值为p1：

结果：

说实话，原地的真不好想，我也是别人给我讲的，但是我又不会，所以自己先写了一个暴力头插再去理解，发现就是缺什么，创造什么，然后奔着目标去解决问题。

三、链表中间结点

跟链表有关，上快慢指针：

这道题让我们找中间节点，其实就是走整个链表的长度的一半。

先不看题，说一个很简单的例子，如果一段路程一共10米，一个人一次走2米，一个人一次走1米，那怎么才能走到这段路程的一半呢，当然是两个人同时开始走，走的快的人走完了以后，走的慢的人刚好走一半。（我们没有提到的思路是这样的，还拿走路来说，链表长度视为路程，一般的指针就是那个一次走一米的人，让他走完整个链表，每次给一个变量++，就知道整段路多长，然后再根据总长度取半循环，自然就能得到中间结点，但是这么来的话，代码肯定没有我们的快慢指针简单）。

我个人理解快慢指针本质是什么，比如这里，要找到链表一半的结点，免不了去把整个链表遍历一遍，因此就想能不能遍历完就找到了这个位置，所以就有一次走两步和一次走一步的快慢指针的存在了。

经画图，快慢指针的循环条件分为两个，一个是fast != NULL一个是fast ->next != NULL：

当然还有一点问题，循环条件的填写必须这样，因为存在短路问题。

fast && fast -> next

fast先检验是不是空，如果不是再解引用检验fast的next指针是不是NULL，不然在链表长度为偶数时，最终fast已经是空了，按理来说该停止遍历了，但是你如果先验fast->next那就是对空指针的解引用，直接报错了该。

四、合并两个有序链表

题解

其实看着就想用指针来，两个指针遍历原链表，一个新链表的头（最后要返回），一个新链表的尾，因为每次找到的较小元素我们要做的是尾插，记录下来可以免去每次遍历的麻烦。

需要用到的变量以及初始化内容不用多解释。

打眼一看，那就是三种情况呗，如果本次值相同，那就都尾插，并且都向后移：

后面就是谁小插谁。

直接移到末尾，大概看一下循环条件是什么：

因为我们比较值肯定是解引用->来比，这样的话，一旦某一指针遍历到尾，也就是某一指针为空，那就该退出循环了，至于收尾工作，待会再说.

而且经此，转念一想，如果传过来的链表有空那岂不是解引用就错了，所以在循环开始前先写一下限制空链表的语句：

再补上循环条件：

都不为空再进入循环。

出了循环如果有未移的，那就检查一下，再尾插，当然，这个时候就无所谓ptail动不动了，因为这是插的最后一个结点了

最后代码就是这样：

写对归写对了，代码也好理解，就是感觉太长太长了，有点冗余，其实重点就是while循环重复的内容太多了，那为何不看看能不能稍微修改修改，让代码稍简单一点呢。

第一个化简点

一个问题就是，我们选择尾插的时候其实给了三种条件，但是蛮可以改成两种：

也就是说，如果slt2指向的数更小，那就把它尾插到新链表后，其它的不管相等不相等，都尾插slt1，道理很简单，slt1小，尾插人家没啥毛病，slt1和slt2指向的相等，那无论先插谁了：

比如这样，你先插了slt1里面的1，下次还是能轮着slt2，毕竟不尾插，不后移。

改进思路就是，明显不等情况加一起就是相等情况，所以不妨用不等代替等。

第二个化简点

观察到，外层if-else语句产生的原因是，链表为空和非空的尾插不同，实际上为空的尾插只存在一次，那干脆创造一个结点，让他作为我们新链表的头结点，这样就可以做到时时刻刻都是非空尾插，减少分支。

只不过我们创造的非空链表的第一个结点没什么用，所以最后返回的时候还是返回phead->next，并且我们malloc的空间应该用完就还回去，所以这么写：

代码化简以后，明显占的内存也变少了。

五、链表的回文结构

回文结构就是从中间看一个字符串了，数组了，对称，重点就在于对称性。

比如：

inttni

1221

这都是回文结构。

正常题解

问题是怎么判断链表是不是回文结构呢？
这里就要用到我们之前写的那些办法了，一个是找中间结点，毕竟是前后两段对比下来才能看出；一个是反转链表，毕竟回文结构是对称的，我们只能写语句判断是否相等，这样的话就只能先反转一下了。

反转后半段链表的代码和图示

有了这个基础以后，只要遍历着去比较，如果出现不等，直接返回false，如果循环结束没有发现不等，那就return true。

循环条件是什么呢？

不管什么情况下，由于后半段的链表只有原链表的一半，所以应该以遍历后半段链表的值为循环条件：

最终代码为：

投机取巧

看到标题其实就有人想了，什么叫正常题解，什么叫投机取巧。

原因是题目上有一句话：

所以干过的人现在肯定就懂了，单链表的遍历是在是太不方便了，因为不能从右往左，只能从左往后走，回文结构如果用俩指针一个从左往右，一个从右往左，那链表结构根本连改变都不改变。

你给的链表其实没那么大，那我为何不可将你给我的值全部复制到数组里呢，这样不就简简单单对比了，因为int arr[900]也是O（1）啊，别说900,10000也是O（1），空间复杂度可不是看具体的，而是看根据提供的参数造成的额外申请空间的大小。

当然，仅限于内存给的够，链表比较短，不然符合不了它的标准。

六、相交链表

大概读了一下题，题意是两个链表的结点有相同的，也就是说某处开始结点地址完全相同。

其实有点无所适从：

链表相交能有哪几种情况呢？

有点小抽象画的，但是实际上相交就这几种情况，头相交，尾相交，或者中间相交。

要注意，链表相交不要跟数学上的相交混淆：

数学上的相交是这样的，但是链表只要有交点，交点的next指针就是固定的，你再分叉岂不是next指针有两个值了吗。

有了这样的理解，接下来倒着分析：

理想状态下，想的肯定是从前往后遍历找到p1 == p2（结点地址相等），那往后的都该相同了，但是链表长度不相等的话，你一个一个比肯定会错过的啊，那肯定得让链表较长的遍历指针(比如这个例子的p2)先走几步，等到等长了再一起往后走，但是你咋能知道提前走多少呢、

其实上面做过一道题用快慢指针的时候确实有类似于一个先一个后的关系，但是那道题是给定了找中间结点，一个走两个一个走一个就行，这是空间上的快慢。

我们现在要的是什么，要的是一个指针先走，一个指针后走，这样的话等于是时间上的快慢。

怎么才能知道先走几步呢，我上面其实说了，我们现在做的题其实都免不了去遍历整个链表，因为你要对链表操作，总得每一个结点的去对照符不符合插入了，删除了，对比了之类的问题。

所以既然我们要想知道先走几步，那不就是算算长链表和短链表差几个结点嘛，遍历结点不就知道了嘛，只不过得用变量存一下链表的长度：

同步以后，就简单了：每次进入循环比较一下当前结点位置，不一样就后移，一样就返回，出了循环就说明根本没有相同的结点，那就返回NULL就行：

七、判断链表中是否有环

直接给出了，就是快慢指针法：

一个指针走2步，一个指针走1步，如果不存在环，那么肯定快指针先碰见NULL，如果存在环，两个指针不管怎样都会入环，入环以后，不管距离怎样，两个指针的距离肯定是慢慢缩小的（假设slow入环后两指针距离为N，那么继续走就是N + 1 - 2，N + 1 - 2 + 1 - 2 ...2 + 1 - 2， 1 + 1 -2），那终会相遇，一旦相遇就有环。