题解 | #输出单向链表中倒数第k个结点#

双指针法

#include <iostream>
using namespace std;

struct ListNode{
    int val;
    ListNode* next;
    //三种不同参数的构造函数
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x):val(x), next(nullptr){};    
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

int nodeVal(ListNode*, int);   //函数提前声明一下
int main(){
    int cnt_node;   //链表节点个数
    int val;   //链表节点值
    int k;   
    while(cin >> cnt_node){
        ListNode* head = new ListNode(-1);   //链表的头结点
        ListNode* p = head;    //工作指针
        //创建单链表     ！！！！！！！！！！！！！！！！！
        for(int i = 1; i <= cnt_node; i++){   
            cin >> val;
            ListNode* tmp = new ListNode(val);
            tmp->next = nullptr;
            p->next = tmp;
            p = tmp;
        }
        cin >> k; 
        int res = 0;
        if(k >= 1)
            res = nodeVal(head->next, k);//因为创建的是带头节点的单链表(head没有实际意义），
                                         //所以传入的参数是head->next, 而不是head
        cout << res <<endl;
    }
    return 0;
}

//查找链表的倒数第k个节点
int nodeVal(ListNode* head, int k){
    ListNode* fast = head;
    ListNode* slow = head;
    for(int i = 0; i < k; i++){   //fast先到达第k个节点
        fast = fast->next;
    }
    while(fast != nullptr ){   //使slow最终到达倒数第k个节点
        fast = fast->next;    //注意fast与slow的顺序
        slow = slow->next;
    }
    return slow->val;
}