转载

给Java程序员的20个链表面试题

全文共 4258 字，预计学习时长 8 分钟

给Java程序员的20个链表面试题

图片来源： unsplash.com/@d_mccullough

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

什么是链表？

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

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

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

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

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

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

给Java程序员的20个链表面试题

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

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

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

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

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

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

谨记：如果你不具备任何数据结构基础知识，或近期没有对其进行重温，那么解决这些基于链表的编程问题是没有意义的。在这种情况下，建议你通过优秀的数据结构与算法课程（https://javarevisited.blogspot.com/2018/11/top-5-data-structures-and-algorithm-online-courses.html）或课本（https://javarevisited.blogspot.com/2015/07/5-data-structure-and-algorithm-books-best-must-read.html）来复习这个概念。

给Java程序员的20个链表面试题

Java面试中20大链表问题

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

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

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

答案：http://javarevisited.blogspot.sg/2012/12/how-to-find-middle-element-of-linked-list-one-pass.html

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

答案：http://javarevisited.blogspot.sg/2017/03/how-to-reverse-linked-list-in-java-using-iteration-and-recursion.html

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

答案：https://www.geeksforgeeks.org/remove-duplicates-from-an-unsorted-linked-list/

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

答案：http://javarevisited.blogspot.sg/2016/05/how-do-you-find-length-of-singly-linked.html

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

答案：http://javarevisited.blogspot.sg/2013/05/find-if-linked-list-contains-loops-cycle-cyclic-circular-check.html

6. 如何反转链表？

答案：http://www.java67.com/2016/07/how-to-reverse-singly-linked-list-in-java-example.html

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

答案：http://javarevisited.blogspot.sg/2016/07/how-to-find-3rd-element-from-end-in-linked-list-java.html

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

答案：https://www.geeksforgeeks.org/sum-of-two-linked-lists/

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

答案：http://www.java67.com/2017/06/5-difference-between-array-and-linked.html

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

答案：https://leetcode.com/problems/remove-nth-node-from-end-of-list/solution/

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

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

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

答案：http://www.java67.com/2016/02/how-to-sort-linkedlist-in-java-example.html

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

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

答案：https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/solution/

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

答案：https://leetcode.com/problems/partition-list/solution/

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

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

答案：https://leetcode.com/problems/intersection-of-two-linked-lists/solution/

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

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

答案：https://leetcode.com/problems/remove-duplicates-from-sorted-list/solution/

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

给Java程序员的20个链表面试题

程序面试的有用资源

给Java程序员的20个链表面试题

图片来源： unsplash.com/@charlesdeluvio

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

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

传送门：https://click.linksynergy.com/fs-bin/click?id=JVFxdTr9V80&subid=0&offerid=323058.1&type=10&tmpid=14538&RD_PARM1=https%3A%2F%2Fwww.udemy.com%2Fdata-structures-and-algorithms-deep-dive-using-java%2F

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

传送门： https://www.educative.io/collection/5668639101419520/5671464854355968?affiliate_id=5073518643380224

3. 程序员面试金典

传送门： http://www.amazon.com/Cracking-Coding-Interview-6th-Edition/dp/0984782850/?tag=javamysqlanta-20

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

传送门： https://click.linksynergy.com/deeplink?id=JVFxdTr9V80&mid=39197&murl=https%3A%2F%2Fwww.udemy.com%2Fcourse%2Fmaster-the-coding-interview-data-structures-algorithms%2F

5. 为面试做准备-John Sonmez

传送门： https://pluralsight.pxf.io/c/1193463/424552/7490?u=https%3A%2F%2Fwww.pluralsight.com%2Fcourses%2Fdeveloper-job-interviews

给Java程序员的20个链表面试题

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

想要在面试中获得成功，无论公司大小，编程工作级别高低，常见的编程（http://www.java67.com/2018/05/top-75-programming-interview-questions-answers.html），数据结构（https://hackernoon.com/50-data-structure-and-algorithms-interview-questions-for-programmers-b4b1ac61f5b0）与算法问题（https://dev.to/javinpaul/50-data-structure-and-algorithms-problems-from-coding-interviews-4lh2）都是面试者必须掌握的。

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

给Java程序员的20个链表面试题