1、成环问题

题目描述：给定两个可能有环也可能无环的单链表，头结点head1和head2。请实现一个函数，如果两个链表相交，请返回相交的第一个节点。如果不相交，返回null

要求：如果两个链表长度之和为N，时间复杂度请达到O(N)，额为空间复杂度请达到O(1)

  1. 方法一：用set把每个节点的内存地址放到set里面，如果存在相同的内存在set中存在，则就是第一个成环的节点
  2. 方法二：用快慢指针对链表遍历，那么快慢指针一定会相遇，能相遇就说明存在环。然后让慢指针停在相遇的位置，快指针回到头结点。快指针和慢指针再出发且快指针也变成一次走一步和满指针相同，再次相遇的节点就是成环节点

    1.1 方法二分析

    1.1.1 证明方法二的关于找出入环点的方法的正确性

    1、建立模型

    设单链表起点序号为1，入环点序号为k，环中包含L个节点
    例如
    1. 1->2->3->4->5->3
    2. //该单链表入环点k=3，环中包含L=3个节点（3、4、5）

    2、条件假设

    建立快慢指针S、F。S每一个时刻向后移动一位，F每一个时刻向后移动两位
    假设链表长度大于等于3且存在环，起始时S位于节点2，F位于3号节点3

    3、分析

    当S移动至k节点时，此时经历了k-2个时刻，F位于k+（2k-1-k）%L，即环中第p1=1+（k-1）%L个节点。
    假设p1距离入环点还需向后移动d步，则再经历d时刻，S与F相遇在距入环点d步的位置，即环中第p2=d+1个节点，此时重新将F置于节点1，S在环中第p2节点处，并每一时刻F、S都只向后移动一步，S距离入环点p1步（p1+d=L）
    3.1 若tL<k-1<(t+1)L
    则p1=k-1-tL，所以当F从1移动到tL+1时，S循环t圈仍然位于圈中p2节点处
    此时，F距离k恰好为p1步，与S距离入环点k距离相同，故一定会同时相遇在入环点
    3.2 若k<L
    则p1=k,d=L-k,p2=L-k+1
    故S距离入环点L-p2=k-1步，F距离入环点也是k-1步。故S、F一定会相遇在入环点

    4、结论

    综上所述，只要单链表存在环，则构建快慢指针F，S，起始时S位于节点2，F位于节点3，则F与S一定会在环中相遇在某个节点p，此时重置F=1，S=p，步速统一向后移动一位，则F、S下次必定在入环点相遇，得证。