题目的主要信息：

根据题意，输入一个单向链表，输出该链表中倒数第k个结点。

方法一：

我们首先补充一下节点结构，使之能够赋值初始化。而后我们按照顺序建立链表，首先建立头节点，再不断的往链表后增加节点，形成单向链表。题目要求输出倒数第k个节点，我们知道这个链表总共有n个节点，倒数第k个节点即为正数第n-k+1个节点，因此我们从头节点出发，往后遍历，在第n-k+1个节点停下，输出当前节点的值。

具体做法：

#include<iostream>

using namespace std;
struct ListNode//节点结构
{
    int val;
    ListNode* next;
    ListNode(int x):val(x),next(NULL){}
};

int main(){
    int n;
    while(cin>>n){
        ListNode *h=new ListNode(0);//头节点
        ListNode *p=h;//用于创建链表
        int num;
        for(int i=0;i<n;i++){//创建链表
            cin>>num;
            ListNode *node=new ListNode(num);
            p->next=node;//连接当前链表的最后一个节点和新节点
            p=p->next;
        }
        int k;
        cin>>k;
        num=n-k;//输出倒数第k个即正数第n-k个
        ListNode *q=h;
        while(num>=0){//从头开始走n-k步到达第n-k+1个节点
            q=q->next;
            num--;
        }
        if(q!=NULL){//若第n-k节点不为NULL，输出这个节点的值
            cout<<q->val<<endl;
        }else{
            cout<<0<<endl;
        }
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(n)O(n)$，创建链表需要遍历一遍。
• 空间复杂度：$O(1)O(1)$，除了链表外，只用了常数空间。

方法二：

我们可以先定义两个指针，fast和slow，初始化这两个指针指向头结点。用while循环让fast指针先走k步，等fast走完k步后，到达第k+1个节点，还剩下n-k-1个节点没有走，slow指针从这时开始向前走，两个指针同时向前走，直到fast指针为NULL，fast和slow节点一起走了n-k步，slow指针此时在正数第n-k+1位，若slow指针不为NULL，slow所指的节点即为倒数第k个节点。 具体做法：

#include<iostream>

using namespace std;
struct ListNode//节点结构
{
    int val;
    ListNode* next;
    ListNode(int x):val(x),next(NULL){}
};

int main(){
    int n;
    while(cin>>n){
        ListNode *h=new ListNode(0);//头节点
        ListNode *p=h;//用于创建链表
        int num;
        for(int i=0;i<n;i++){//创建链表
            cin>>num;
            ListNode *node=new ListNode(num);
            p->next=node;//连接当前链表的最后一个节点和新节点
            p=p->next;
        }
        int k;
        cin>>k;
        num=n-k;//输出倒数第k个即正数第n-k个
        ListNode *slow=h;//慢指针
        ListNode *fast=h;//快指针
        while(k>0){//快指针先走k步
            fast=fast->next;
            k--;
        }
        while(fast!=NULL){//快慢指针一起走，直到快指针达到结尾
            fast=fast->next;
            slow=slow->next;
        }
        if(slow!=NULL){//若慢指针不为NULL，输出这个节点的值
            cout<<slow->val<<endl;
        }else{
            cout<<0<<endl;
        }
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(n)O(n)$，创建链表需要遍历一遍。
• 空间复杂度：$O(1)O(1)$，除了链表外，只用了常数空间。