Question

node fun(node *head,int n),其中node是一个单向链表。求实现功能：返回倒数的第n个节点。

请写出详细代码。非程序员勿答。谢谢

Answer 1

1） 单独设置一个指针用于记录需要记录的节点的地址，不妨命名为 seekn，初始时令其指向链表的首节点。另外一个临时节点用于从头到尾遍历整个链表，初始值也指向首节点。
node *seekn=head;
node *tmp=head;
2） 构建一个遍历链表的循环。比如使用
int i=0;
while(NULL != tmp)
{
i++; //记录当前遍历到了第i个节点
tmp=tmp->next;

if (i>=n)
seekn=seekn->next; //当i超过n时，seekn指针开始和tmp指针同步向前走，并始终保持间隔n个节点。
}
3）当tmp为NULL时，表示已经遍历到了链表的最后一个节点，跳出了while循环，此时seekn就是你要找的。 当然，如果跳出循环时 i<n，那就意味着链表太短，找不到倒数第n个节点，seekn应当赋予NULL值，这个留给你处理吧。

Answer 2

先遍历看链表中有几个元素，然后返回倒数第n个节点即可。
node fun(node *head,int n)
{
node *p = head;
int i, num = 0;
// 遍历，看链表中有几个元素
while(p)
{
++num;
p = p->next;
}
// 遍历，返回倒数第n个元素
for(i=0; i<num+1-n; i++)
head = head->next;
return *head;
}