Part1

题目

判断链表中是否存在环

141. Linked List Cycle

解法

对于环形链表，设置两个不同速度的指针，fast在多次循环后总能追上slow

    def hasCycle(self, head):
        slow = fast = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if slow == fast:
                return True
        return False

数学证明

Leetcode讨论区有一个很好的解释：https://leetcode.com/problems/linked-list-cycle/discuss/44489/O(1)-Space-Solution
翻译:
１、假定链表直线部分长度为m，环形部分长度为n。
２、当slow行走m步进入环形部分时，fast行进2m路径，此时二者均处于圆环中，且之间的路程差为n-m%n。
３、由于fast和slow之间的速度差为1，所以需要耗时(n-m%n)/1使得fast追上slow。
４、因此，最少需要m+(n-m%n)/1的时间，fast和slow相遇。

思考:
能否利用fast和slow求出环形链表的长度？
回答：
１、求环的长度：设置快慢两个指针，起始位置都是表头。第一次相遇耗时m+(n-m%n)，过m步之后二者再次相遇。借此可以求出环的长度。
２、求环入口：设置两个指针，二者之间的路程差为环长度，且速度都为１，其中一个位于表头出。则两个指针第一次相遇的位置为环的入口。
３、求环入口简洁方法：设置速度为１和２的快慢两个指针，当第一次相遇时，将快指针移动到表头，并降速到１。两个指针第二次相遇的位置为环入口。（可自行推导）

Part２

题目

160. Intersection of Two Linked Lists

解法

１、假设A非共享部分长度为a，B非共享部分长度为b，二者共享部分长度为m。如题目中，a=2，b=3，m=3。
２、设置两个指针pA,pB分别从A,B出发，pA指针到达末尾后进入B，pB指针到达尾部进入A。
３、二者经过一个完整循环后将在c1处相遇，此时行经距离为a+b+m。

    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        ptA, ptB, jumpToNext = headA, headB, False
        while ptA and ptB:
            if ptA == ptB:
                return ptA
            ptA, ptB = ptA.next, ptB.next
            if not ptA and not jumpToNext:
                ptA, jumpToNext = headB, True
            if not ptB:
                ptB = headA
        return None

Part3

升级版链表相交问题

题目描述：判断两个链表（可能有环）是否相交，如果是，确定入口交点。
思路解析：
1.对于listA和listB,分别求出是否有环和环入口nodeA和nodeB（方法参照part1）
2.分三种情况：
　2.1)　listA和listB均无环，参考part2部分。
　2.2)　listA和listB一个有环，一个无环，则肯定不相交。
　2.3)　listA和listB均有环，又可分两种情况：
　　　　2.3.1) 环入口nodeA==nodeB，二环必定相交。去掉环的部分（保留环入口），参照part1求入口交点。
　　　　2.3.2) 环入口nodeA!=nodeB，如果二点均在同一个环内，则相交，交点即为环入口；否则不相交。

带环链表相交.jpeg