全文共4258字，預計學習時長8分鐘
圖片來源：unsplash.com/@d_mccullough今天，本文將詳細介紹編程面試中常見的鍊表問題。
什麼是鍊表？
數據結構在程序面試中極其重要。鍊表則是對數組數據結構進行的補充，是另一種常見的數據結構。和數組相似的是，鍊表也是線性數據結構，並以線性方式儲存元素。
但是，和數組不同的是，鍊表不將元素儲存在連續的位置；相反，其元素分散在內存中的各個地方，並以節點進行相互連接。
鍊表不過是一個節點的列表，其中每一個節點都包含存儲的值和下一個節點的位置。
正是因為其結構，在鍊表中添加與刪除元素變得尤為簡單，比起創建數組，它只需要簡單的更改連結。但是搜索難度很大，且通常需要增加等同的時間成本（隨著數據量的增大）才能在一個單一鍊表內找到某個元素。
此文章給出了更多數組與鍊表數據結構之間的差異：http://javarevisited.blogspot.sg/2013/07/difference-between-array-and-linked-list-java.html
鍊表也有很多種類型，比如單鍊表，允許向一個方向（向前或向後）移動；雙鍊表，允許向兩個方向（向前或向後）移動；最後是循環鍊表，形成了一個圓。
如何在面試中解決鍊表編程問題？
為了解決基於鍊表的問題，有必要充分了解遞歸，因為鍊表就是一個遞歸數據結構。
如果從鍊表中取一個節點，剩餘數據結構仍然構成一個鍊表。也正是因此，許多鍊表問題的遞歸解決方案比迭代解決方案更加簡單。
這些問題也可以用分而治之的技巧解決，將一個問題分成多個子問題，直到能完全解決它們。
比如說，要反轉一個鍊表，可以不斷將其斷開，直到只有一個節點為止。這時，你知道如何反轉只有一個節點的鍊表。鍊表不過就是同一個節點。
這與遞歸非常相似，實際上，你能解決的最小子問題就是遞歸解決方案的基本情況。
謹記：如果你不具備任何數據結構基礎知識，或近期沒有對其進行重溫，那麼解決這些基於鍊表的編程問題是沒有意義的。在這種情況下，建議你通過優秀的數據結構與算法課程（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大鍊表問題
下面列出了技術面試中一些最常見且受歡迎的鍊表面試問題，有些已經附上了答案，但仍然建議你先自己嘗試解決問題。
如果解決了問題或在嘗試之後陷入困境，可以看看解決方案並從中學習相關知識。
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/
這些問題將幫助你提升解題能力並提高對鍊表數據結構的了解。
程序面試的有用資源
圖片來源：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
恭喜！你離準備好編程面試更近了一步
想要在面試中獲得成功，無論公司大小，編程工作級別高低，常見的編程（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）都是面試者必須掌握的。
以上的資料為準備面試提供了很好的主題，也有助於評估面試者的準備工作並找出其強項與弱點。
留言 點讚 發個朋友圈
我們一起分享AI學習與發展的乾貨
編譯組：段昌蓉、劉賀
相關連結：
https://dzone.com/articles/20-linked-list-interview-questions-for-java-progra
如需轉載，請後臺留言，遵守轉載規範
推薦文章閱讀
長按識別二維碼可添加關注
讀芯君愛你