# 面试题9：单链表中倒数第k个结点

```/*     思路1：链表中倒数第k个结点    */
{
int num = 0;
while(p != NULL)
{
num++;
p = p->next;
}
if(num == 0 || k > num)
return NULL;

for( int i = 0; i < num-k; i++)
{
p = p->next ;
}
return p;
}```

```/*     思路2：链表中倒数第k个结点    */
{
int num = 0;
Node *p1, *p2;
while(p != NULL)
{
num++;
p = p->next;
}
if(num == 0 || k > num)
return NULL;

p1 = p2 = head; //开始p1和p2都指向头结点
for(int i = 0; i< k; i++)
{
p1 = p1->next;
}
while(p1 != NULL)
{
p1 = p1->next;
p2 = p2->next;
}
return p2;
}```

```#include<iostream>
#include <stack>
#include<stdlib.h>
#include<time.h>

using namespace std;

typedef struct node
{
int data;
struct node *next;
}Node;

/*     创建含有n个结点的单链表    */
{

/* 初始化随机数种子 */
srand(time(0));  //srand函数在stdlib.h头文件中，time函数在time.h头文件中

for(int i=0; i < n; i++)
{
Node *p = (Node *)malloc(sizeof(Node));
p->data = rand()%100+1;  //随机生成100以内的数字
p->next = q->next;
q->next = p;
q = p;
}
q->next = NULL;

}

/****打印单链表******/
{
Node *p;
{
cout << "The LinkList is Empty !" <<endl;
return;
}
while(p!=NULL)
{
cout << p->data << " " ;
p=p->next;
}
}
/*     思路1：链表中倒数第k个结点    */
{
int num = 0;
while(p != NULL)
{
num++;
p = p->next;
}
if(num == 0 || k > num)
return NULL;

for( int i = 0; i < num-k; i++)
{
p = p->next ;
}
return p;
}

/*     思路2：链表中倒数第k个结点    */
{
int num = 0;
Node *p1, *p2;
while(p != NULL)
{
num++;
p = p->next;
}
if(num == 0 || k > num)
return NULL;

p1 = p2 = head; //开始p1和p2都指向头结点
for(int i = 0; i< k; i++)
{
p1 = p1->next;
}
while(p1 != NULL)
{
p1 = p1->next;
p2 = p2->next;
}
return p2;
}
int main()
{
int length;

cin >> length;
cout << "The new created LinkList as below: " ;
cout << endl;

Node *KthNode = NULL;
int kth;
cout << "思路1：请输入要查找的倒数第几个节点:  " ;
cin >> kth;
cout << "链表倒数第" << kth << "个结点为：" << KthNode->data <<endl;

cout << "思路2：请输入要查找的倒数第几个节点:  " ;
cin >> kth;