经典面试题之链表
- 《程序员面试金典》p49,2.6, 求单链表环路的入口结点。
- 相关题目：给定两个单链表，求他们的共同交点。 解法： （1）利用栈，空间复杂度高 （2）先对两个链表分别作就地反转，然后再一次判断 （3）先分别遍历两个链表，如果能遍历到相同的尾结点，则两个链表相交，同时记录下两条链表的长度longlength和shortlength，然后用两个指针fast和slow；fast先走(longlength-shortlength)步，然后他们再同时走，到相同时就是第一个相交结点 （4）将两个链表首尾相连，然后转换为“求单链表中环路的开头结点”的问题。时间复杂度O(M+N)
- 给定单链表头结点，删除链表中倒数第k个结点 分析：这道题可转换为查找链表中倒数第k+1个结点；只需要注意k+1和链表的长度，注意其中的错误检查即可
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2014.06.20 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读