The sword refers to the offer question 22 - the Kth node from the bottom in the linked list

假设有n个节点,Then calculate the penultimatek个节点的值,要用双指针
思想：
n个节点,倒数第k个节点.可以画一个图,有9个元素,分别有

a[0]=0
a[1]=1
a[2]=2
a[3]=3
a[4]=4
a[5]=5
a[6]=6
a[7]=7
a[8]=8

然后假设k=3,A指针指向倒数第k个元素6,BThe pointer points to the end element8
So the subscript distance between the two pointers is always differentk-1=2个（This is easy to derive,因为倒数第k个和末尾元素下标The distance between is necessary减去第koccupied by an element1个位置,减1是容易推导的）,So when you analyze this relationship,你把A BThe pointers are respectively translated to point to the first element of the linked list,第1elements go backwardsk-1The position of the element of the step,Then the two pointers are separated again同步依次遍历next指针,Traversing to the end is our initial situation,此时AThe pointer happens to point to the first of the linked listk个的位置

因此,要保证B指针和APointers always differk-1的距离,就要先把Bpointer movesk-1次,Then double pointer synchronization is facilitated untilB指针的next为nullptr

最后代码如下,problem22.h是声明,problem22.cpp是函数的实现,最后main.cpp是main函数
problem22.h

#ifndef PROBLEM_PROBLEM22_H
#define PROBLEM_PROBLEM22_H
#include <iostream>

struct node {
    
    int value;
    struct node *next;
    node(int value){
    
        this->value=value;
        this->next= nullptr;
    }
};

typedef struct node *pnode;
typedef unsigned int uint;

pnode FindKthToTail(pnode pListHead, uint k) ;
void add(pnode& head,int value);
void print(pnode h);
/** * * * @return A pointer to the head of a linked list */
pnode init();
#endif //PROBLEM_PROBLEM22_H

problem22.cpp

#include <iostream>
#include "problem22.h"


typedef node *pnode;
typedef unsigned int uint;

pnode FindKthToTail(pnode pListHead, uint k) {
    
    pnode pAhead = pListHead;
    pnode pBehind = nullptr;
    for (int i = 0; i < k - 1; ++i) {
    
        pAhead = pAhead->next;
    }
    pBehind = pListHead;
    while (pAhead->next != nullptr) {
    
        pAhead = pAhead->next;
        pBehind = pBehind->next;
    }
    return pBehind;
}
void add(pnode& head,int value){
    
    if(head== nullptr){
    
        head=new node(value);
        return;
    }
    pnode ptr=head;
    while (ptr->next!= nullptr){
    
        ptr=ptr->next;
    }
    pnode new_node=new node(value);
    ptr->next=new_node;
    return;
}

void print(pnode h){
    
    pnode ptr=h;
    while (ptr){
    
        printf("%d " ,ptr->value);
        ptr=ptr->next;
    }
}
/** * * * @return A pointer to the head of a linked list */
pnode init(){
    
    pnode head=new node(1);
    add(head,2);
    add(head,3);
    add(head,4);
    add(head,5);
    add(head,6);
    add(head,7);
    add(head,8);
    add(head,9);
// add(head,10);
// print(head);
    return head;
}

main.cpp

#include <iostream>
#include "problems/problem22.h"
using namespace std;
int main() {
    
    std::cout << "Hello, World!" << std::endl;
    pnode hA = init();

    pnode node = FindKthToTail(hA,3);
    printf("%d",node->value);
    return 0;
}