总结方法，高效进步

经过几天的线上练习，也做了许多练习题，但想要高效进步，不只是需要简简单单的练习，还需要的是要学会总结，以下是有关链表遇到问题的总结。

问题1：求链表中倒数第K个节点

解题思路：定义两个指针p1，p2，开始都指向链表头位置，然后先将P1向前移动K个位置。之后p1，p2同时向前移动，直到P1到链表尾部。此时p2的位置就是倒数第K个。

问题2：判断链表中是否存在环

解题思路：定义两个快慢指针p_fast， p_slow， 初始时都指向链表头结点。然后p_fast以每次两步向前移动。p_slow以每次一步向前移动。如果在移动过程中两指针相遇，则表示存在环。否则链表中不存在环。（当然还有一种解题思路是也是用hash方法来判断链表中是否存在环）

问题3：判断存在环的链表中环的长度

解题思路：两个快慢指针相遇时一定会在环中相遇，根据问题2，当两个指针相遇时，保持快指针不动，然后让慢指针一次以一步的速度移动，当快慢指针再次相遇时慢指针走过的路程便是环的长度（可以想象在一个圆中两个点相遇，然后一个点不动，另一个点继续移动，当两个点相遇时，移动的那个点走过的距离便是圆的周长）

问题4：求存在环的链表中环的入口

解题思路：通过问题3我们知道了怎么求环的长度。假设求得环的长度为n，然后用类似于问题1的解题思路，设两个指针p1，p2分别指向链表头，然后p1向前移动n个位置。之后p1，p2同时向前移动。当p1和p2相遇时 p1（或p2）指向的位置即为环的入口位置

注意：要判断类似A-B-C-A这种情况的存在。

问题5：判断两个链表是否相交

解题思路：首先分别判断两个链表是否存在环。

（1）如果两个链表都不存在环，则直接比较两个链表的表尾节点是否相等即可，如果相等，则相交，否则不想交。

（2）如果一个链表存在环，而另一个链表不存在环，则两个链表肯定不相交.

（3）如果两个链表都存在环。则如果两个链表相交的话则一个链表肯定共用环。通过判断一个链表中任意一个环内节点是否在另一个链表中即可判断两个链表是否相交。

“君子博学而日参省乎己”，不断反思总结才会走的更远，才会离目标越来越近。

（供稿人：王丽莹）

http://www.dxsbao.com/shijian/353535.html 点此复制本页地址