[LeetCode]鏈表中倒數第k個結點
- 題目
- 分析
- 代碼
- 總結
題目
輸入一個鏈表，輸出該鏈表中倒數第k個結點，
鏈接：https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&&tqId=11167&rp=2&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking
分析
我們在解決這道題目之前，我們先回顧一下雙指標思路的講解https://blog.csdn.net/weixin_52664715/article/details/120746151?spm=1001.2014.3001.5501
我們在學習了雙指標的解決思路之后，我們面對這一型別的題目首選任然是雙指標方法去解決，那么我們應該怎樣使用該方法去解決呢？
我們分析題目知道，題目要求我們找到倒數第k個結點，那么我們的首要問題就是這么去找到這個位置，我們任然舉例追擊相遇的問題，在橋上，有兩輛相同的自行車，兩車的移動速度相同，但我們讓一輛自行車先向前移動3m，那么我們現在再讓兩車同時出發，那么最終的結果是出發距離提前的自行出先到達，同時后面的自行車與已經到達的自行車之間的距離仍為3m
那么我們在解決這道問題也是相同的，我們仍然設定兩個指標，一個快指標fast，一個慢指標slow，但這一次我們不再是讓快指標每一次移動k個距離單位，而是讓我們的快指標先移動k個單位距離之后，快慢指標一起移動
此時我們遍歷我們的鏈表，直至fast指標先移出鏈表范圍，此時我們的slow指標指向的位置就是我們鏈表中倒數的k個結點
但是我們仍要考慮一些特殊情況，當我們讓fast指標先移動時，如果我們的要查找倒數第9個數，可是我們的鏈表中只含有3個元素時，我們是沒有這個元素的，那么我們就要增加判斷代碼
代碼
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k )
{
ListNoed* fast,*slow;
fast = slow = pListHead;
while(k--)//我們先讓fast指標向前移動
{
if(fast = NULL)//判斷如果我們當前fast指標指向為NULL，那么我們就回傳，查找不到；這里就解決了我們上面提到的鏈表中只含有3個元素，但我們卻要找倒數第9個元素，當fast移動4個單位距離時，fast指標指向的就是NULL，此時我們結束，回傳NULL
return NULL;
fast = fast->next;
}
while(fast)
{
fast = fast->next;
slow = slow->next;
}
return slow;
}
總結
快慢指標在我們資料結構中的鏈表問題經常使用，也是十分經典的解決方法，我們這里就不在是簡單的雙指標的直接應用，多了一些分析，在后面的問題中會經常使用，在后面我也會繼續分析與記錄
以上就是我對這種方法的個人理解
上述內容如果有錯誤的地方，還麻煩各位大佬指教【膜拜各位了】【膜拜各位了】
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/316627.html
標籤：其他