【每日编程】Day 2求链表倒数第k个结点的值

问题描述

已知一个带有表头结点的单链表，结点结构为：

假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功，算法输出该结点的data域的值，并返回1;否则，只返回0。

解决方法

（1）算法的基本思想：

从头至尾遍历单链表，并用指针p指向当前结点的前k个结点。当遍历到链表的最后一个结点时，指针p所指向的结点即为所查找的结点。

（2）详细步骤：

详细实现步骤:增加两个指针变量和一个整型变量，从链表头向后遍历，其中指针p1指向当前遍历的结点，指针p指向p1所指向结点的前k个结点

如果p1之前没有k个结点，那么p指向表头结点。用整型变量i表示当前遍历了多少个结点，

当i>k时，指针p随着每次遍历，也向前移动一个结点。

当遍历完成时，p或者指向表头结点，或者指向链表中倒数第k个位置上的结点。

（3）代码实现：

#include<stdio.h>
#include<stdlib.h>
typedef struct Node
{
	int data;
	struct Node *next;
}Node,*LinkList;
LinkList CreateList(int n)
{
	LinkList h,r,s;
	h=(LinkList)malloc(sizeof(Node));
	r=h;
	int i;
	int x;
	for(i=0;i<n;i++)
	{
		s=(LinkList)malloc(sizeof(Node));
		scanf("%d",&x);
		s->data=x;
		r->next=s;
		r=s; 
	}
	r->next=NULL;
	h=h->next;
	return h;
}
void PrintList(LinkList L)
{
	while(L)
	{
		printf("%d\t",L->data);
		L=L->next;
	}
	printf("\n");
}
LinkList FindElement(LinkList list,int k)
{
	LinkList p,p1;
	p=list;
	p1=list->next;
	int i=1;
	while(p1)
	{
		p1=p1->next;
		i++;
		if(i>k)
			p=p->next;
	}
	if(p==list)
		return 0;
	else
	{
		printf("%d\n",p->data);
	}
}
int main()
{
	LinkList L1;
	int n,k;
	printf("请输入L1链表的长度，以回车结束，然后输入结点的值：");
	scanf("%d",&n);
	L1=CreateList(n);
	printf("L1链表为：");
	PrintList(L1);
	printf("请输入k的值：");
	scanf("%d",&k);
	printf("倒数第%d个结点为：",k);
	FindElement(L1,k);
	printf("\n");
	return 0; 
}