Java 数据结构——单链表面试题（二）

Java 数据结构——单链表面试题（二）

本次内容介绍大纲

在这里插入图片描述

  接上篇 Java 数据结构——单链表面试题（一）

  在上一篇文章中，我们介绍了单链表的几道简单面试题，这次我们将继续通过简单的单链表面试题(以牛客网及 Leetcode 的链表题为主)来深入了解 单链表的知识结构。

一、链表中倒数第k个结点

1.题目要求

在这里插入图片描述

举一个例子：

  我先提供一个 已有的链表结构

在这里插入图片描述

  我们现在提供 给一个整形参数 k = 2 ，找到这个链表结构中的倒数第二个节点 。

2.思路实现

思路一

在这里插入图片描述

思路二

在这里插入图片描述

这种思路我们在实际链表中 走一遍…

设置 fast 、slow 指向head 头节点

在这里插入图片描述

fast 先走 k-1 步， slow 保持不动

在这里插入图片描述

slow、fast 同时向后走，直到 fast 为指为null

在这里插入图片描述

  此时 slow 指向的就是 我们题目所求的链表的 倒数第 2 个节点。

  返回 slow。

  好的 思路二能够找到倒数第 K 个节点，我们来就具体实现其每一个步骤的具体思路

1.首先我们传入参数 k 值，要考虑 k的合法性

2.slow、fast 的实际操作

在这里插入图片描述

  但是 ，上面的代码思路仍然有缺陷，在判断 k 的合法性时， 如果 k > sizeof() ,我们要调用 sizeof() 函数，此时也是一次 遍历链表的过程，所以 遍历次数两遍，也不符合要求。

  我们还要继续调整…

在这里插入图片描述

在这里插入图片描述

  这样的思路过程就没有问题了，整体代码遍历一遍。

3.代码实现

在这里插入图片描述

二、合并两个有序链表

1.题目要求

在这里插入图片描述

我们提供两个已知的有序链表

在这里插入图片描述

按照题目要求，最终按照升序 返回一个合并的链表

在这里插入图片描述

2.思路实现

在这里插入图片描述

3.代码实现

在这里插入图片描述

三、链表分割

1.题目要求

在这里插入图片描述

在这里插入图片描述

2.思路实现

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

3.代码实现

在这里插入图片描述

四、删除链表中重复的结点

1.题目要求

在这里插入图片描述

2.思路实现

在这里插入图片描述

在这里插入图片描述

3.代码实现

在这里插入图片描述

  好了今天的知识就分享到这里，希望大家多多练习，谢谢大家的欣赏与关注！！

感谢支持！！！

   之后的单链表面试题博主会持续进行更新，欢迎各位读者大大的关注哦！！

未完待续…