leetcode 面试题 02.02. 返回倒数第k个节点

提建议就是，有些题还是有联系的，建议就收看完 876.链表的中间节点（http://t.csdnimg.cn/7axLa），再将这一题联系起来

面试题 02.02. 返回倒数第k个节点

题目：

实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。

说明：

给定的 k 保证是有效的。

题目链接

力扣（LeetCode）官网 – 全球极客挚爱的技术成长平台

文字 和 画图 分析

这题和快慢指针有点像（返回 876.链表的中间节点）,我们定义两个指针 fast指针 和 slow指针，都存放头节点的地址

这里我们有两种思路：

1. fast 先比 slow 多走 k 步，然后同时走完链表（放循环里面）
2. fast 先比 slow 多走 k – 1 步，然后同时走完链表（放循环里面）

第一种思路：

结束条件：

fast ==NULL

第二种思路：

结束条件：

fast->next == NULL

代码

代码一（思路一）：

int kthToLast(struct ListNode* head, int k)
{
    struct ListNode*slow = head;
    struct ListNode*fast = head;
    while(k--)
    {
        fast = fast->next;
    }
   while(fast)
   {
       fast = fast->next;
       slow = slow->next;
   }
    return slow->val;
}

 代码二（思路二）：

int kthToLast(struct ListNode* head, int k)
{
    struct ListNode*slow = head;
    struct ListNode*fast = head;
    while(--k)
    {
        fast = fast->next;
    }
   while(fast->next)
   {
       fast = fast->next;
       slow = slow->next;
   }
    return slow->val;
}