【LeetCode刷题（简单程度）】面试题 02.02. 返回倒数第 k 个节点_leetcode刷到什么程度

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

注意：本题相对原题稍作改动

示例：

输入： 1->2->3->4->5 和 k = 2
输出： 4
说明：

给定的 k 保证是有效的。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/kth-node-from-end-of-list-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路1：无脑搞先，利用栈的FILO将链表反序233333。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    int kthToLast(ListNode* head, int k) {
        stack<int>s;
        ListNode *p = head;
        while(p)
        {
            s.push(p->val);
            p = p->next;
        }
        for(int i = 1;i < k;++i)
        {
            s.pop();
        }
        return s.top();
    }
};

思路2：快慢指针，p1和p2首先都指向head，然后p1先遍历到第k个，遍历到第k个之后p2再和p1一起遍历，等p1遍历完的时候，p2刚好指向倒数第k个节点。（O(n)）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    int kthToLast(ListNode* head, int k) {
        ListNode *p1 = head;
        ListNode *p2 = head;
        for(int i = 0;i<k;i++)
            p1 = p1->next;
        while(p1)
        {
            p1 = p1->next;
            p2 = p2->next;
        }
        return p2->val;
    }
};