/*
有一个带头结点的单链表，设计一个函数找到指定的倒数第k个节点，输出节点值，并返回1，否则返回0，前提不能改变链表，尽可能高效
分析：
我们可以先统计出总共的节点数count，那么该节点的顺序数num=count-k+1,当然如果k>count,直接返回0，时间复杂度为O(n)
这里还有另一种更加便捷的方法，只需对链表遍历一次，我们设立两个指针，最开始均指向首节点，然后让q先移动k个节点，之后p
q同步移动，当q为NULL时，p所在的位置便是倒数第k个节点的位置
*/
#include<stdio.h>
#include<stdlib.h>
typedef struct LNode //定义单链表的节点类型
{
int value; //数据域
struct LNode *next; //指针域
}LNode,*Linklist;
Linklist list_TailInsert(Linklist &L) //采用尾插法建立单链表，正向建立单链表
{
int value; //设元素类型为整型
L = (Linklist)malloc(sizeof(LNode));
L->next = NULL;
LNode *head = L,*rear = L;//head头指针，rear尾指针
printf("请输入链表各节点的值，以9999结束：");
scanf("%d",&value); //输入节点的值
while(value != 9999)//依次创建节点
{
LNode *s;
s = (Linklist)malloc(sizeof(LNode));
s->value = value;
s->next = NULL;
rear->next = s;
rear = s;
scanf("%d",&value);
}
rear->next = NULL;//尾结点指针置空
return L;
}
void Display(struct LNode *L1)
{
struct LNode *p = L1->next;
while (p != NULL)
{
printf("%d ",p->value);
p = p->next;
}
}
int findTheReciprocalk(Linklist &L,int k)
{
LNode *p = L->next,*q = L->next;
while(k-1 != 0)
{
if(p == NULL)
{
printf("输入K值有误！！！");
return 0;
}
p = p->next;
k--;
}
while(p != NULL)
{
p = p->next;
q = q->next;
}
printf("倒数第%d个位置结点的值：%d",k,q->value);
return 1;
}
int main()
{ struct LNode *L1;
list_TailInsert(L1);
printf("打印单链表：");
Display(L1);
int k;
printf("请输入要查找倒数第几个结点：");
scanf("%d",k);
findTheReciprocalk(L1,k);
return 0;
}
修改好了,while(k-1!=0)改成while(k>0)，main函数里面输入k那句少了个取地址符号&，应该是scanf("%d", &k);
#include<stdio.h>
#include<stdlib.h>
typedef struct LNode //定义单链表的节点类型
{
int value; //数据域
struct LNode *next; //指针域
}LNode, *Linklist;
Linklist list_TailInsert(Linklist &L) //采用尾插法建立单链表，正向建立单链表
{
int value; //设元素类型为整型
L = (Linklist)malloc(sizeof(LNode));
L->next = NULL;
LNode *head = L, *rear = L;//head头指针，rear尾指针
printf("请输入链表各节点的值，以9999结束：");
scanf("%d", &value); //输入节点的值
while (value != 9999)//依次创建节点
{
LNode *s;
s = (Linklist)malloc(sizeof(LNode));
s->value = value;
s->next = NULL;
rear->next = s;
rear = s;
scanf("%d", &value);
}
rear->next = NULL;//尾结点指针置空
return L;
}
void Display(struct LNode *L1)
{
struct LNode *p = L1->next;
while (p != NULL)
{
printf("%d ", p->value);
p = p->next;
}
}
int findTheReciprocalk(Linklist &L, int k)
{
LNode *p = L->next, *q = L->next;
int d = k;
while (k > 0)
{
if (p == NULL)
{
printf("输入K值有误！！！");
return 0;
}
p = p->next;
k--;
}
while (p != NULL)
{
p = p->next;
q = q->next;
}
printf("倒数第%d个位置结点的值：%d", d, q->value);
return 1;
}
int main()
{
struct LNode *L1;
list_TailInsert(L1);
printf("打印单链表：");
Display(L1);
int k;
printf("请输入要查找倒数第几个结点：");
scanf("%d", &k);
findTheReciprocalk(L1, k);
return 0;
}