一、单链表

1.判断两个链表有没有相交,如果有相交，返回第一个相交节点，没有返回NULL；

根据观察图片我们发现，如果两个链表有相交部分，那么最后一个节点地址必定相等，如果没有相交最后一个节点地址不相等。

当两个相交链表的长度相等时，两个指针分别往后面走，当它们相遇时，相遇的节点就第一个相交节点。

代码实现如下:

2.判断一个链表有没有环，如果有环返回第一个入环节点，没有环返回NULL；

第一步:判断链表有没有环?

判断链表有没有环，用快慢指针。如果链表有环，那么快指针和慢指针必定相遇，没有环，快指针一定比慢指针先到链表的尾部。

第二步:有环就找到第一个入环节点，没有返回NULL

先假设有如图带环链表；并在头结点处定义一个fast和一个slow指针（快慢指针），每次让fast走两步，slow走一步；则在环中，它们会在B点相遇，A点则为链表入环的第一个节点。

那么怎么找到第一个入环节点呢?

先说结论:当快慢指针第一次相遇时，令快指针回到头节点，慢指针在原地不动，然后快慢指针同时移动，快指针一次走一步，慢指针一次走一步，当它们再次相遇时，相遇的节点就是第一个入环节点。

数学证明如下图:

1.假设链表长度为n；head到入口点A的距离为x；入口点A到相遇点B的距离为y;
2.因为fast所走的路程是slow所走路程的两倍，即有：fast = 2 * slow;
3.fast和slow相遇后，fast所走的路程为：链表的总长度加上入口点A到相遇点B的距离，即：fast = n + y;slow走的路程为head到相遇点的距离，即：slow = x + y;

4.fast = 2 * slow; fast = 2(x + y) = n + y;

消元得n = x + x + y;

所以相遇点b到第一个入环节点的距离也为x;

代码实现如下：