`
ipython
  • 浏览: 294571 次
  • 性别: Icon_minigender_1
  • 来自: 佛山
社区版块
存档分类
最新评论

单链表的倒数第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个元素的指针), 这样,遍历时就不用从头到尾遍历一次啦。

 

 

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

 

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

分享到:
评论
Global site tag (gtag.js) - Google Analytics