### 這節的鏈表是無環的(有環的鏈表通過當前節點的m_next 是不是環的入口節點來判斷有沒有到達最后一個節點,為什么要判斷到達最后一個節點,請看下面的思路)。
### 思路:先說明一點,k 從 1 開始計數,所以沒有倒數第 0 個節點。利用鏈表節點的距離(兩個節點可以通過幾步到達,相鄰節點可以通過一個m_next直接到達,所以步數是 1)不會變的特點,倒數第 k 個節點通過 k - 1 步可以到達最后一個節點,那么如果有兩個指針,一個從鏈頭出發,一個先從鏈頭走 k - 1 步, 然后兩個指針同時向前走,當前面一個指針到達最后一個節點時,那么后面一個指針就是倒數第 k 個節點。
下面是代碼實現:
```
SList* findLastKthNode(SList *list, unsigned int k)
{
if (list == nullptr || k == 0) {
return nullptr;
}
SList *slow = list, *fast = list;
// 快指針先走 k - 1 步
for (unsigned int i = 0; i < k - 1; ++i) {
if (fast->m_next != nullptr) {
fast = fast->m_next;
} else { // k 大于鏈表的長度
return nullptr;
}
}
// 同時走,有環的話判斷條件得改為fast->m_next != 環入口點
while (fast->m_next != nullptr) {
fast = fast->m_next;
slow = slow->m_next;
}
return slow;
}
```