- 《程序员面试金典》p49,2.6, 求单链表环路的入口结点。
- 相关题目：给定两个单链表，求他们的共同交点。
解法：
（1）利用栈，空间复杂度高
（2）先对两个链表分别作就地反转，然后再一次判断
（3）先分别遍历两个链表，如果能遍历到相同的尾结点，则两个链表相交，同时记录下两条链表的长度longlength和shortlength，然后用两个指针fast和slow；fast先走(longlength-shortlength)步，然后他们再同时走，到相同时就是第一个相交结点
（4）将两个链表首尾相连，然后转换为“求单链表中环路的开头结点”的问题。时间复杂度O(M+N) - 给定单链表头结点，删除链表中倒数第k个结点
分析：这道题可转换为查找链表中倒数第k+1个结点；只需要注意k+1和链表的长度，注意其中的错误检查即可
网友评论