图片来源：unsplash.com/@d_mccullough

今天，本文将详细介绍编程面试中常见的 链表 问题。

什么是链表？

数据结构在程序面试中极其重要。链表则是对数组数据结构进行的补充，是另一种常见的数据结构。和数组相似的是，链表也是线性数据结构，并以线性方式储存元素。

但是，和数组不同的是，链表不将元素储存在连续的位置；相反，其元素分散在内存中的各个地方，并以节点进行相互连接。

链表不过是一个节点的列表，其中每一个节点都包含存储的值和下一个节点的位置。

正是因为其结构，在链表中添加与删除元素变得尤为简单，比起创建数组，它只需要简单的更改链接。但是搜索难度很大，且通常需要增加等同的时间成本（随着数据量的增大）才能在一个单一链表内找到某个元素。

此文章给出了更多数组与链表数据结构之间的差异：http:// Java revisited.blogspot.sg/2013/07/difference-between-array-and-linked-list-java.html

链表也有很多种类型，比如 单链表 ，允许向一个方向（向前或向后）移动；双链表，允许向两个方向（向前或向后）移动；最后是循环链表，形成了一个圆。

如何在面试中解决链表编程问题？

为了解决基于链表的问题，有必要充分了解递归，因为链表就是一个递归数据结构。

如果从链表中取一个节点，剩余数据结构仍然构成一个链表。也正是因此，许多链表问题的递归解决方案比迭代解决方案更加简单。

这些问题也可以用分而治之的技巧解决，将一个问题分成多个子问题，直到能完全解决它们。

比如说，要反转一个链表，可以不断将其断开，直到只有一个节点为止。这时，你知道如何反转只有一个节点的链表。链表不过就是同一个节点。

这与递归非常相似，实际上，你能解决的最小子问题就是递归解决方案的基本情况。

谨记：如果你不具备任何数据结构基础知识，或近期没有对其进行重温，那么解决这些基于链表的编程问题是没有意义的。在这种情况下，建议你通过优秀的数据结构与 算法 课程（）或课本（）来复习这个概念。

Java面试中20大链表问题

下面列出了技术面试中一些最常见且受欢迎的链表面试问题，有些已经附上了答案，但仍然建议你先自己尝试解决问题。

如果解决了问题或在尝试之后陷入困境，可以看看解决方案并从中学习相关知识。

1. 如何在一次传递中找到单链表的中间元素？

答案：

2. 如何在不使用递归的情况下反转单链表？

答案：

3. 如何删除一个未排序链表中的重复节点？

答案：

4. 如何找出一个单链表的长度？

答案：

5. 如何查找链表是否包含循环？如何找出循环开始节点？

答案：

6. 如何反转链表？

答案：

7. 如何找到单链表中的倒数第三个节点？

答案：

8. 如何使用栈计算两个链表的和？

答案：

9. 如何在适当的位置反转链表？

答案：

10. 如何移除链表中的倒数第N个节点？

答案：

11. 如何合并两个排序的链表？

12. 如何在链表中添加元素？

13. 如何在Java中实现链表排序？

答案：

14. 数组和链表有什么区别？

15. 如何将排序列表转化为 二分查找 树？

答案：

16. 给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。

答案：

17. 如何在整数链表中删除所有与给定值相等的节点？

18. 如何找到两个单链表相交的起始节点？

答案：

19. 如何判断一个链表是否是回文结构？

20. 如何从排序链表中删除重复项？

答案：

这些问题将帮助你提升解题能力并提高对链表数据结构的了解。

程序面试的有用资源

图片来源：unsplash.com/@charlesdeluvio

如果需要一些有用的资源来帮助搞定程序和编程工作面试，以下是一些值得一看的网络资源和书籍：

1. 数据结构与算法：用Java进行深入研究

传送门：

2. 摸索编程面试：编程问题模式

传送门：

3. 程序员面试金典

传送门：

4. 精通编码面试：数据结构+算法

传送门：

5. 为面试做准备-John Sonmez

传送门：

恭喜！你离准备好编程面试更近了一步

想要在面试中获得成功，无论公司大小，编程工作级别高低，常见的编程（），数据结构（）与算法问题（）都是面试者必须掌握的。

以上的资料为准备面试提供了很好的主题，也有助于评估面试者的准备工作并找出其强项与弱点。

留言 点赞 发个朋友圈

我们一起分享AI学习与发展的干货

编译组：段昌蓉、刘贺

相关链接：

如需转载，请后台留言，遵守转载规范