前面兩篇文章主要介紹了，快慢指標在鏈表環中的應用，除此之外，我們還常常利用快慢指標來查找單向鏈表中指定位置的節點，
常見的經典題目有：
1、查找倒數i位置的的節點
2、查找中間節點
我們依次來看
一、查找快慢指標查找單鏈表中位于倒數第i個位置的元素
力扣 劍指 Offer 22. 鏈表中倒數第k個節點 （https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/）
如果沒有提前做過準備，想要解決類似問題，只能通過快取等方式來解決，但是通過快慢指標，可以很巧妙的解決該問題，
思路是這樣的：(防盜連接：本文首發自http://www.cnblogs.com/jilodream/ )
快慢指標同時指向head節點，接著慢指標不動，快指標向前移動i步，之后快慢指標同速前移動，直至快指標先到終點，此時慢指標，所處的位置就是倒數第i個節點的位置，
就像下圖，假設右側小人先跑40m，隨后兩者同速前進，則左側小人距離右側小人始終為40m，這樣當右側小人到達終點時，左側小人的位置恰好為倒數40m處：
代碼也很簡單：
1 public ListNode getKthFromEnd(ListNode head, int k) { 2 ListNode fast = head; 3 ListNode tail = head; 4 for (int i = 0; i < k-1; i++) { 5 fast = fast.next; 6 } 7 while (fast.next != null) { 8 fast = fast.next; 9 tail = tail.next; 10 } 11 return tail; 12 }
這個場景其實除了雙指標的解法，還可以通過遞回出堆疊的方式解決，感興趣的同學可以自己想想
二、查找鏈表中間位置的節點
力扣 876. 鏈表的中間結點 （https://leetcode.cn/problems/middle-of-the-linked-list/）
此題與上題類似，仍然可以采用快慢指標的形式，
區別是不再同速保持固定距離，而是快指標每次走兩步，慢指標走一步，
這樣假設快指標遍歷了2N個節點，慢指標就是便宜了N個節點，
如果你自己考慮這個問題，你會發現事情沒有這么簡單：
這里會涉及到兩個問題：(防盜連接：本文首發自http://www.cnblogs.com/jilodream/ )
1、鏈表長度是不是偶數，
2、鏈表如果是偶數，那么中間節點應該是中間位置左側節點 還是右側節點，
如果鏈表長度奇數的話，那么要注意快指標最后一次移動是不能走兩步的，
如果鏈表長度是偶數的話，我們取中間位置的右側節點，代碼如下：
1 public ListNode middleNode(ListNode head) { 2 ListNode fast = head; 3 ListNode low = head; 4 while (true) { 5 if (fast.next == null) { 6 return low; 7 } 8 low = low.next; 9 fast = fast.next; 10 if (fast.next != null) { 11 fast = fast.next; 12 } 13 } 14 }
細想一下，這種思路其實除了可以找到中間節點位置，還可以找到1/3處節點位置，1/5處節點位置，
如果你覺得寫的不錯，歡迎轉載和點贊， 轉載時請保留作者署名jilodream/王若伊_恩賜解脫（博客鏈接：http://www.cnblogs.com/jilodream/
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/506033.html
標籤：其他