剑指offer第22题-链表中倒数第K个节点

假设有n个节点，则计算倒数第k个节点的值，要用双指针
思想：
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，B指针指向末尾元素8
因此两个指针之间的下标距离始终相差k-1=2个（这个容易推导，因为倒数第k个和末尾元素下标之间距离就是要减去第k个元素所占的1个位置，减1是容易推导的），因此当你分析出这个关系，你把A B指针分别平移指向链表第一个元素，第1个元素往后走k-1步的元素的位置，然后两个指针再次分别同步依次遍历next指针，遍历到最后就是我们最初的情况，此时A指针恰好指向链表第k个的位置

因此，要保证B指针和A指针始终相差k-1的距离，就要先把B指针先后移k-1次，然后双指针同步便利直到B指针的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 一个链表的头指针 */
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 一个链表的头指针 */
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;
}