?？途W(wǎng) 鏈表中倒數(shù)第k個結點

題目描述

描述

輸入一個鏈表，輸出該鏈表中倒數(shù)第k個結點。

思路分析

這是一道經(jīng)典的快慢指針題，fast和slow最開始都指向頭結點，對于輸入值k，先讓快指針fast先走k步，之后再讓兩個指針一起走，最后slow指向的就是對應的結點。

我的理解就是利用slow與fast的差值形成一個區(qū)間，將這個區(qū)間進行遍歷，當快指針遍歷到尾時，相當于從倒數(shù)第一個開始往前找slow。

完整代碼

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {struct ListNode* slow=pListHead;struct ListNode* fast=pListHead;while(k--){if(fast==NULL){return NULL;}fast=fast->next;}while(fast){fast=fast->next;slow=slow->next;}return slow;}