数据结构——链表OJ题目讲解（1）

作者：几冬雪来

时间：2023年3月7日

内容：数据结构链表OJ题目讲解

题目来源：力扣和牛客

目录

前言：

刷题：

1.移出链表元素：

2.链表的中间结点：

3. 链表中倒数第k个结点：

结尾： 

---

前言：

在上一篇博客中我们对链表内容的讲解也就结束了，但是链表作为我们一个难度跨度较大的一个专题，因此单单看是不行的。在学习链表的过程中，如果要进一步提升自己，刷题是必不可少的一个环节。

刷题：

在学习数据结构的过程中，刷题能够提高我们写题的能力，帮助我们以后在在找工作的时候可以游刃有余，同时也可以检验出我们的不足之处，在写的时候还会有一些平常没有遇到的坑在等着我们，下面我就找来了力扣和牛客上找来一些有关链表的题目来讲解。 

1.移出链表元素：

 

题目要求删除链表中的某一数据，看似我们在写链表的代码中也有类似的操作，只不过它们还是有点不同。在我们书写的链表代码中，只是删除一次val而已，而这个题目则需要我们删除所有val，二者有所区别。

而在刷数据结构的题的时候，画图是我们一定要学会的一种技能。 那么这一题的运行是怎么样的呢？

因为是链表，因此一开始我们创建两个指针，prev指针指向我们第一个结点，cur指向第二个结点。 如果cur等于val的话，我们就将cur->next赋值给prev->next，然后将cur的值释放。

这里我们将代码写出来，先创建两个空指针，一个置为空，一个指向第一个结点的位置，然后进行循环，循环条件是cur不为0。再下来就进行判断，如果cur的下一个结点不为val,则把cur赋予给prev，再让cur来到下一个结点。

如果cur为val，则只需要将原cur的下一个结点的地址赋值给prev的next，后将cur释放。最后把prev->next赋值给cur，让它依旧指向prev的下一个结点。 

这里要注意最后应该是cur = prev->next，如果是cur = cur->next的话，我们会访问到空指针。 

代码到这里就结束了吗？我们运行出来看一看，但是这里的结果却十分出乎意料。

我们的案例并没有通过，这是为什么？这就需要分析一下了。我们从这个题目的用例中取一个用例来说明。

类似这个用例，假设第一个结点就是我们要删除的值，这个时候我们上面的代码if语句条件不满足进入else语句。然而因为if语句没有进行，我们的prev的值依旧为空，下面prev->next=cur->next就会出错。所以我们要对代码进行分开讨论。

就像上面的代码这样，如果第一个if语句条件不成立，那么就进入else语句中。这里我们在分支语句中再嵌套一个分支语句。如果我们的prev为空，那就说明第一个结点的值就是要删除的值。然后这里将我们的头结点改为cur->next，而后将cur释放，最后因为头结点的删除，因此要将head赋值给cur作为指向新的头结点的指针。

结果证明我们的想法是正确的。

其实对于这道题目，我们还有其他的解决方法。这里我们可以将不是val的值尾插到新链表。

像我们这张图，我们创建一个新链表newHead并在一开始将它置空。如果第一个结点不为val，则我们让cur = tail，作为我们新指针的头结点。而后cur向下移动，如果不为val则给新的链表然后tail也向下移动，如果不是则跳过这个值。

依旧开始创建指针，下来函数循环。如何cur指向的不是val，则进入if语句中进行嵌套的分支语句。

而这里的嵌套的分支语句中，if语句只执行一次，当tail为空的时候，也就说明我们的新指针里面还没有值，这里就要将cur赋值给tail和newHead作为新指针的头结点。（尾插要赋值） 

再然后让tail->next指向cur也就是第二个结点，接下来tail向下走一步来到第二个结点的位置，cur向下走一步来到cur的下一个结点。 

如果找到val的值的话，我们就创建一个临时指针next，然后将cur下一个结点赋值给next，next就是cur的下一个结点，为的是保存我们这个结点。赋值完了之后我们将cur释放掉，然后将next赋值给cur。 

看似没有问题，但是实际上是会出错的，而链表中如果出问题的话，那么十有八九是野指针的存在。

其实是这个代码出了问题，也不能说是问题，只能说不完整。那么为什么会不完整呢？在怎么的这个题目中最后一个数据是要删除的，然后在代码的这个地方，我们创建了一个临时变量来保存cur的下一个结点，然后将cur释放最后cur = next。但是我们tail->next依旧存在着原来没删除前值的地址，而后我们将其释放，这里就会变成一个空指针形式。

而要解决这个问题也是十分简单。 

在循环结束后我们将tail->next置空即可，这样就避免了野指针的出现。 书写完了之后我们再次运行程序，但是很遗憾这里我们的代码函数存在问题。

 

从代码用例我们可以分析出，这是链表为空的情况，如果链表为空，这里我们程序的循环就不会运行。然后tail->next = NULL这个地方就出错了。

要修复这个问题其实也是十分的简单，只要在程序的开头对我们的链表是否为空进行判断即可。 

但是即使这样，我们的代码依旧有问题存在。 

当我们的代码全是7，删除的也是7的时候，这个时候代码也会出错。那个时候我们的代码会将全部结点删除掉了，没有结点尾插，newHead和tail依旧为空，还是tail->next = NULL这个地方的问题。 那么代码还是需要改进。

在这里我们用一个分支语句将它包裹住，如果结点全部删除tail为空，这个代码也不会执行程序也就不会出问题。再次运行程序看看结果。

终于在我们改了好多次之后，我们的代码终于运行成功了。下面我们就将我们的代码全部放上来。 

这道题我们到这里就结束了。下面还有一道题目需要我们解决。

2.链表的中间结点：

这道题是人我们求链表的中间结点的值，而解决这道题的方法有许多中。类似我们的最传统的方法，先计算链表的长度然后找中间值。 

又因为这道题目过于简单，因此这道题通常都有一些限制所在。例如：只能遍历一遍链表。如果是这样的话，那么上面的传统方法就不用了。 

同样的这道题也可以通过创建数组来解决，但是那种方法就类似于顺序表的写法，比起链表过于复杂。 为了比较快速的解决这道题，这里我们要了解一个解题方法——快慢指针。那么什么是快慢指针呢？

 

快慢指针的工作原理就类似我们上边这个图，一开始创立一个快指针和一个慢指针都指向头结点，而后开始移动快指针一次移动两步，慢指针则一次移动一步。快指针的移动速度是慢指针的两倍，因此当指针fast走完的时候，slow刚刚好久到了链表的中间。

然而这个代码还有另一个影响因素，那就是数组的个数为单数还是偶数。如果链表的结点个数是单数，则中间结点就只有一个，如果结点个数为偶数则中间结点有两个，依题得知如果中间结点个数为两个我们要取后面的那个结点。

我们要将它进行分类讨论。 

先创建两个指针，两个指针都指向链表的头结点。因为fast走的比slow指针要快，因此我们选用fast指针作为循环条件判断。

两种判断的原理如图所示。而后就是循环，slow每次走一步，fast指针每次走两步，最后返回slow指针。运行起来看看结果。

通过测试可以看出我们的想法没有问题，也可以成功输出。

下一道题目则是来自我们的牛客网的题库。 

3. 链表中倒数第k个结点：

 

 这一题函数运用我们的快慢指针，只不过和上面的比较时间的快慢不一样，在这里我们比较的是个数。那么个数是怎么样快慢的呢？首先我们要知道一个点。

尾结点和倒数第k个结点之间的距离是k-1。

那么解决这道题就有两种方法，我们画个图出来看看。

 

这就是我们的解题原理，既然倒数第k个结点和尾结点之间的距离是k-1。那么在快慢指针中我们就可以先让快指针先走k-1步，而后快指针和慢指针同时向后运行距离相差k-1，当我们的fast走到尾结点的时候，这个时候slow就是倒数第k个结点。

也可以让fast先走k步，最后slow要在倒数第k个结点处的话，fast要指向空。两种方法都是可以的。而这个问题我采用了第二种方法。

首先先对链表为空进行处理，接下来还是创建两个指针并都指向链表的头结点。然后先一个循环来让fast先走k步，最后再创建一个循环来让两个指针同时往后走，并在结束的时候返回slow的指针。

但是这里我们的代码是不完全的，那它还存在什么问题呢？ 在调试中我们可以看出如果在这里想要访问倒数第6个的结点，但是链表总共才5个数据，这样做就造成了空指针的问题。 那要怎么样修改呢？

 

改动的地方就是这里，如果fast为0了，我们直接返回空。但是我们的用例不止一个地方报错。在第二个用例处我们依旧报错了。

其实这里的问题更加容易解决。这里是因为的fast赋值比判断先执行，导致了第二个用例本来指向最后一个结点指向了最后一个结点后面的空。fast变为了空，因此我们要将这个判断语句调整到执行语句的上面。

 

这个问题也就得到解决了。 

依旧我们将书写的代码放过来。

 

到这里这篇博客要刷的题就结束了。

结尾： 

通过今天刷的链表的题目，我们对链表的知识得到了进一步的提高，题目里面的有些坑也值得我们去深思，一些日常学习看起来微不足道的点，在正式写代码的时候可能就会出现致命的错误。如果想要更加提升自己链表能力的同学也可以多去找题目写。最后希望这篇博客能在写题的时候为各位提供帮助。