题目的主要信息：

• 输入一个单向链表，输出该链表中倒数第k个结点
• 链表的倒数第1个结点为链表的尾指针
• 异常返回空指针
• k为0输出0

方法一：根据长度找倒数k

具体做法：

正常遍历，根据输入连接链表，一共n个值，链表长度为n。 然后比较链表长度是否比k小，如果比k小返回一个空链表，否则遍历n-k次即可找到所求。

#include<iostream>
using namespace std;

struct ListNode{ //链表结点
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL){} //初始化
};
ListNode* FindKthToTail(ListNode* pHead, int k, int n) { //找到链表倒数第k个结点
    ListNode* p = pHead;
    if(n < k) //长度过小，返回空链表
        return p = NULL;
    for(int i = 0; i < n - k; i++) //遍历n-k次
        p = p->next;
    return p;
}

int main(){
    int n;
    while(cin >> n){ //输入n
        int val;
        cin >> val;
        ListNode *head = new ListNode(val); //链表第一个结点
        ListNode *p = head;
        for(int i = 1; i < n; i++){ //输入链表后续结点
            cin >> val;
            ListNode *q = new ListNode(val);
            p->next = q; //连接
            p = p->next;
        }
        int k;
        cin >> k; //输入k
        if(k == 0) //k等于0直接输出0
            cout << 0 << endl;
        else{
            p = FindKthToTail(head, k, n); //找到第k个结点
            if(p != NULL) //返回不为null才能输出
                cout << p->val << endl;
        }
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O\left(n\right)O(n)$O(n)，输入构建链表要遍历一次，找到倒数第$kk$k个结点，最坏要遍历$nn$n次
• 空间复杂度：$O\left(1\right)O(1)$O(1)，链表空间属于必要空间，无额外空间

方法二：快慢双指针

具体做法：

我们准备快慢双指针，都从链表头出发，快指针先行k步，达不到k步说明链表过短，返回空链表。然后快慢指针同步向后，快指针先到底，慢指针指向倒数第k个，因为它们之间差了k个元素。

#include<iostream>
using namespace std;

struct ListNode{ //链表结点
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL){} //初始化
};
ListNode* FindKthToTail(ListNode* pHead, int k) {//找到链表倒数第k个结点
    int n = 0;
    ListNode* fast = pHead;
    ListNode* slow = pHead;
    for(int i = 0; i < k; i++){  //快指针先行k步
        if(fast != NULL)
            fast = fast->next;
        else //达不到k步说明链表过短，返回空链表
            return slow = NULL;
    }
    while(fast != NULL){ //快慢指针同步，快指针先到底，慢指针指向倒数第k个
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

int main(){
    int n;
    while(cin >> n){ //输入n
        int val;
        cin >> val;
        ListNode *head = new ListNode(val); //链表第一个结点
        ListNode *p = head;
        for(int i = 1; i < n; i++){ //输入链表后续结点
            cin >> val;
            ListNode *q = new ListNode(val);
            p->next = q; //连接
            p = p->next;
        }
        int k;
        cin >> k; //输入k
        if(k == 0) //k等于0直接输出0
            cout << 0 << endl;
        else{
            p = FindKthToTail(head, k); //找到第k个结点
            if(p != NULL) //返回不为null才能输出
                cout << p->val << endl;
        }
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O\left(n\right)O(n)$O(n)，总共遍历$nn$n个链表元素
• 空间复杂度：$O\left(1\right)O(1)$O(1)，链表空间属于必要空间，无额外空间