【剑指 offer】链表倒数第k个结点。

1、题目描述

输入一个链表，输出该链表中倒数第k个结点。

注意：

k >= 0;
如果k大于链表长度，则返回 NULL;

样例

输入：链表：1->2->3->4->5 ，k=2
输出：4

2、问题描述：

3、问题关键：

• 这题还是比较简单的，没有让返回删除第k个结点的链表，不用考虑是否是头结点。
• 如果额外的空间的话，可以用一个数组存起来。

4、C++代码：

方法1:只遍历一次，且不用额外的空间。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* findKthToTail(ListNode* head, int k) {
        ListNode *first = head, *second = head;
        while(k -- && first) {
            first = first->next;
        }
        if (k >= 0) return NULL;
        else {
            while(first) {
                first = first->next;
                second = second->next;
            }
            return second;
        }
    }
};

方法2：先求链表的长度，再求倒数第k个结点。

class Solution {
public:
    ListNode *findKthToTail(ListNode *head, int k) {
        int n = 0;
        for (auto p = head; p; p = p->next)  n ++;
        if (n < k) return NULL;
        auto p = head;
        for (int i = 0; i < n - k; i ++) p = p->next;
        return p;
    }
};