一、题目
函数原型：
struct ListNode* FindKthToTail(struct ListNode* pHead, int k )
二、思路
本题需要找到链表中的倒数第k个结点，有两种方法：
1.暴力解法：先遍历一次链表，计算出链表的长度；再遍历一次链表，找到倒数第k个结点。
2.快慢指针：设置一个快指针、一个慢指针，初始时快指针先移动k个结点，然后快慢指针一起移动，当快指针到达空时，慢指针的位置就是倒数第k个结点。
三、代码
代码1（暴力解法）
/** * struct ListNode { * int val; * struct ListNode *next; * }; */ /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param pHead ListNode类 * @param k int整型 * @return ListNode类 */ struct ListNode* FindKthToTail(struct ListNode* pHead, int k ) { // write code here struct ListNode *cur=pHead;//遍历指针 int num=0;//链表长度值 while(cur)//计算链表长度 { num++; cur=cur->next; } if(num==0||k>num)//链表为空，或者k的值超出了链表长度，则返回空 { return NULL; } else//正常情况 { cur=pHead;//遍历指针从头结点开始 for(int i=num-k;i>0;i--)//遍历num-k次找到倒数第k个结点 { cur=cur->next; } return cur;//返回倒数第k个结点 } }
代码2（快慢指针）
/** * struct ListNode { * int val; * struct ListNode *next; * }; */ /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param pHead ListNode类 * @param k int整型 * @return ListNode类 */ struct ListNode* FindKthToTail(struct ListNode* pHead, int k ) { // write code here if (pHead == NULL) //链表为空，直接返回空 { return NULL; } else //链表不为空 { struct ListNode* slow = pHead;//慢指针 struct ListNode* fast = pHead;//快指针 for (int i = 0; i < k; i++) //快指针先走k个结点 { if(fast)//快指针不为空，说明k值没有超过链表长度 fast = fast->next; else//快指针为空，说明k值超过了链表长度，直接返回空 { return NULL; } } while (fast) //快慢指针一起走，当快指针为空时，慢指针就到达了倒数第k个结点 { slow = slow->next; fast = fast->next; } return slow; } }
