剑指offer22—链表中倒数第k个节点

本文主要是介绍剑指offer22—链表中倒数第k个节点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

剑指offer22—链表中倒数第k个节点

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点

思路：

本题可利用双指针的思想，先让两个指针p、q均指向第一个结点，接着让p先走到链表中k的位置，那么p与q的距离为k，接着让两个指针同时向前走，当p走到null的时候，q恰好处于倒数第k个位置

头文件如下：

#pragma once
#include<iostream>
using namespace std;
class Node{
public:int data;Node* next;
};
class Linklist {
public:Linklist();void Creatlist();void Showlist();Node* GetlastK(int k);
private:Node* head;
};

具体实现如下：

#include<iostream>
#include<ctime>
#include"反转链表元素.h"
using namespace std;
Linklist::Linklist()
{head = new Node;head->data = 0;head->next = NULL;
}
void Linklist::Creatlist()
{Node* p = head;int n = 5;for (int i = 0; i < n; i++){Node* q = new Node;q->data = rand() % 100;q->next = NULL;p->next = q;p = q;}
}
void Linklist::Showlist()
{Node* p = head;int i = 0;while (p->next != NULL){p = p->next;cout << p->data << "->";i++;}cout << "NULL"<<endl;
}
Node* Linklist::GetlastK(int k)
{Node* p = head->next;Node* q = head->next;for (int i = 0; i < k; i++){p = p->next;}while (p != NULL){p = p->next;//最后p是指向null的q = q->next;}return q;
}
int main()
{srand((unsigned int)time(NULL));Linklist l;l.Creatlist();l.Showlist();cout << "----------------------" << endl;/*Node* temp = l.Reverselist();l.Showreverselist(temp);*/int n;cout << "您想查看倒数第几个结点的数据？" << endl;cin >> n;Node* temp = l.GetlastK(n);cout << "倒数第" << n << "个元素为：" << temp->data << endl;
}