|
1. 倒数第K个元素。
思路：设有两个指针 p 和 q，初始时均指向头结点。首先，先让 p 沿着 next 移动 k 次。此时，p 指向第 k+1个结点，q 指向头节点，两个指针的距离为 k 。然后，同时移动 p 和 q，直到 p 指向空，此时 q 即指向倒数第 k 个结点。
2. 获取链表中间元素。
思路：设有两个指针 fast 和 slow，初始时指向头节点。每次移动时，fast向后走两次，slow向后走一次，直到 fast 无法向后走两次（此时fast.next = None 或 fast.next.next = None)。这使得在每轮移动之后。fast 和 slow 的距离就会增加一。设链表有 n 个元素，那么最多移动 n/2 轮。当 n 为奇数时，slow 恰好指向中间结点，当 n 为 偶数时，slow 恰好指向中间两个结点的靠前一个。
3. 判断链表是否有环。
思路：设有两个指针 fast 和 slow，初始时指向头节点。每次移动时，fast向后走两次，slow向后走一次。若fast无法再向后走，则链表中不存在环。若fast和slow相遇，则存在环。此时fast比slow多走了1或2个环。
4. 寻找链表环的入口。
思路：设有两个指针 fast 和 slow，初始时指向头节点。每次移动时，fast向后走两次，slow向后走一次。若fast无法再向后走，则链表中不存在环。若fast和slow相遇，则存在环。此时将fast指向head，之后将fast和slow每次走一步向后移动，两个指针再次相遇时即为环的入口。
5. 计算链表中环的长度。
思路：设有两个指针 fast 和 slow，初始时指向头节点。每次移动时，fast向后走两次，slow向后走一次。若fast无法再向后走，则链表中不存在环。若fast和slow相遇，则存在环。此时继续移动，二者再次相遇时，满指针走过的步数即为环的长度。
6. 判断两个链表是否相交，相交的话返回相交点。
思路：定义两个指针分别指向两个链表的头部，每次向后移动一位，当两个指针分别第一次走到链表尾部时，使该指针指向另一个链表的头部，继续向后走。如果相交，则两个指针会在变换头部后相遇，第一次相遇点便是相交点。如果变换头部后再次走到链表尾部，说明两个链表不相交。
|