单链表的倒数第n个元素

看到网上的算法面试题，觉得很有趣。

 

输入一个单向链表，输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的尾指针。

 

弄法楚题目后，想了几种方法：

一。先遍历一次单链表,求其长度length，再第二次遍历 length-k 次

二。设置两个指针p1,p2 (p1=p2= p-> head 指向单链表的开始位置)，让第一个指针跑k次 p1 = p1->next, 再一直让p1,p2 执行next，直到p1到达尾部:

    p1 = p2 = head;

    for (int i=0;i<k;i++,p1=p1->next);    

    while (p1)  { p1 = p1->next; p2 = p2->next}  

    return p2;

 

三。对单链表进行索引

 

方法一要遍历两次单链表，当然，如果该单链表的结构不发生变化时，可以保存长度，以备下一次用。

方法二是记录两个指针，这样是遍历一次还是两次链表我也说不清楚 。

方法三，参考数据库中，建立索引的方法， 把单链表的相关信息保存到硬盘。 相关信息有： 单链表的长度，每隔一段距离的开始位置（如保存第1个，第100，第1000个元素的指针), 这样，遍历时就不用从头到尾遍历一次啦。

 

 

方法三，如果该单链表的结构发生变化时，我们要手动维护这些数据，保持一致性。

 

方法一，方法二，网上有解决源代码