单链表输出倒数第k个元素

这个算法已经有不少人写过了，但是为了考研后期复习还是在此记录一下自己的心得。

方法有如下几种：

1、 遍历单链表两次，第一次获取链表总长度，第二次寻找倒数第K个元素就很简单了。但是该方法需要遍历两次链表。

2、 遍历单链表并记录长度，将每个元素存入顺序表中，然后通过下标获取倒数第k个元素。该方法只需遍历一次链表，但是需要额外的存储空间。

3、 既然是倒数第k个元素，那么只要从后往前数k个不就行了。但是又是单链表，获取不到前驱节点。不过，并不需要获取每一个元素的前驱节点，只需要定义两个指针，一个指向最后一个元素，另一个在它前面K个位置即可。而如何实现呢？

typedef int ElemType;
typedef struct LNode
{
    ElemType data;
    struct LNode* next; 
}LNode,*LinkList;

int Search_k(LinkList list, int k)
{
    LNode *p = list->next,*q=list->next;  //p和q一开始都指向第一个节点
    int count =0;  //用于记录p和q之间的距离
    while(p!=NULL)
    {
        if(count<k) k++;
        else q=q->next;
        p=p->next;
    }
    if(count < k)
        return 0;  //数组长度<k
    print(q->data);  //输出q的值
    return 1;
}