单链表

问题1:

如何判断一个单链表中是否存在回路?

解析:

如果一个单链表中存在回路,从头结点开始遍历就会进入死循环,可以通过设置一个快指针与慢指针。快指针每次遍历是P->next->next慢指针每次都是P->next,则如果有回路的话,快指针与慢指针一定会相遇。可以比喻一下两个人跑圈,一个人速度快,一个人速度慢。从同一起点出发,无限的跑下去,那么两个人肯定会有相遇的一刻。

问题2:

如何判断两个单链表是否相交?

解析:

两个单链表相交的状态,肯定是从某一个节点开始,两个单链表共同拥有这段链表,直到尾节点结束。

PS:遇到单链表的问题,最好是在纸上画一下,把单链表的状态画出来,找出其中的特征