经典面试题之链表

  1. 《程序员面试金典》p49,2.6, 求单链表环路的入口结点。
  2. 相关题目：给定两个单链表，求他们的共同交点。
    解法：
    （1）利用栈，空间复杂度高
    （2）先对两个链表分别作就地反转，然后再一次判断
    （3）先分别遍历两个链表，如果能遍历到相同的尾结点，则两个链表相交，同时记录下两条链表的长度longlength和shortlength，然后用两个指针fast和slow；fast先走(longlength-shortlength)步，然后他们再同时走，到相同时就是第一个相交结点
    （4）将两个链表首尾相连，然后转换为“求单链表中环路的开头结点”的问题。时间复杂度O(M+N)
  3. 给定单链表头结点，删除链表中倒数第k个结点
    分析：这道题可转换为查找链表中倒数第k+1个结点；只需要注意k+1和链表的长度，注意其中的错误检查即可
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容