JSMS25-输出单链表倒数第N个节点的值-剑指offer15

分析，这道题目可以采用遍历两遍然后得到长度，然后输出。当然也可以遍历一遍就可以得到结果，具体就是通过一个指针p1在前面遍历，p2指针和p1之间的长度差为N个，这样p1遍历结束之后，p2所指向的就是倒数第N个节点。

#include <stdio.h>
#include <stdlib.h>

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

node *Creat(int *a,int len)
{
	node *head=(node *)malloc(sizeof(node));
	head->data=NULL;
	node *ret=head;
	for(int i=0;i<len;i++)
	{
		node *s=(node *)malloc(sizeof(node));
		s->data=a[i];
		s->next=NULL;
		head->next=s;
		head=s;	
	}		
	return ret;
} 

void Print(node *h)
{
	for(h=h->next;h;h=h->next)
	{
		printf("%d->",h->data);
	}
}

int FindX(node *h,int num)
{
	node *tmp=h;
	int i,ret;
	for(i=0;h;h=h->next,i++)
	{
		if(i>=num)
		{
			tmp=tmp->next;
		}
	}
	if(i<num)       //这里当i小于num的时候，说明链表长度低于n，返回-1
	{
		ret=-1;
	}else
	{
		ret=tmp->data;
	}
	return ret;
}

int main()
{
	int a[]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
	int len=sizeof(a)/sizeof(a[0]);
	node *h=Creat(a,len);
	Print(h); 
	int n=5;
	int ret=FindX(h,n);
	printf("\nThe num is %d\n",ret);
} 











复制代码