先理解一下题目的意思，单链表的相交和普通两条线的相交一样吗？



所以当我们把其换成节点就可以变成下面这样：


先判断链表是否相交，我们可以运用两个链表相交后就变成了一条链表这个特性来判断，因为如果两条链表相交，那么这两条链表的最后一个节点一定是同一个节点，否则不可能相交
	//1表示有交点，0表示没有交点
	int IsIntersection(Node *first1, Node *first2)
	{
		assert(first1);
		assert(first2);
		while (first1->next != NULL)
		{
			first1 = first1->next;
		}
		while (first2->next != NULL)
		{
			first2 = first2->next;
		}
		if (first1 == first2)
		{
			return 1;
		}
		return 0;
	}


接下来，我们考虑交点的问题，如何才能找到交点？

两条链表在交点之后的长度肯定是一样的，在交点之前的长度是不一样的，我们可以计算出两条链表长度的差值k，然后让长的链表先走k步，再让两条链表同时走，当相同的时候，就表示走到交点了，这时候返回即可


	int GetLength(Node *first)
	{
		assert(first);
		int count = 0;
		while (first != NULL)
		{
			count++;
			first = first->next;
		}
		return count;
	}

	Node *IntersectionNode(Node *first1, Node *first2)
	{
		assert(first1);
		assert(first2);
		int count1 = GetLength(first1);
		int count2 = GetLength(first2);
		Node *longer = first1;
		Node *shorter = first2;
		int k = count1 - count2;
		if (count1 < count2)
		{
			longer = first2;
			shorter = first1;
			k = count2 - count1;
		}
		while (k--)
		{
			longer = longer->next;
		}
		while (longer != shorter)
		{
			longer = longer->next;
			shorter = shorter->next;
		}
		return longer;
	}

问题：链表
链表结构，判断是否有环
解决方法：快慢双指针
经典的双指针方法，一个指针每次向后移动两个节点，一个指针每次向后移动一个节点，如果链表有环，最终两个指针会碰到一起，
主要问题：有环链表，能找出环的切入口节点吗？
也是利用快慢双指针，不过技巧在于，第一次相遇后，如果从头节点再来一个慢指针，两个慢指针相遇的节点就是入口节点，有点抽象，我们来形象描述一下，如下图：


这是第一次相遇的时候，我们根据快慢指针可以得到公式：

$\begin{aligned}
2*(k+m)&=k+L+m \\
2k+2m&=k+L+m \\
k&=L-m
  \end{aligned}$
这里可以看到 $k=L-m$，此时相遇点到入口节点的距离正好等于头节点到环的入口的距离，所以此时从头节点安排一个慢指针出发，两个慢指针肯定能相遇，而且相遇的节点就是在环的入口。

题目
给定一个链表，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。 否则，返回 false 。

进阶：

你能用 O(1)（即，常量）内存解决此问题吗？

示例 1：



输入：head = [3,2,0,-4], pos = 1

输出：true

解释：链表中有一个环，其尾部连接到第二个节点。
来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/linked-list-cycle

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路：快慢指针
//解法：快慢指针法，慢指针一次走一步，快指针一次走两步，快指针先进环，慢指针后进环，当环很小，而链子很长的时候，快指针会在环里一直跑圈。

//当慢指针进入环的时候，快指针可能在环上任意一点，这时，开始追击问题，假设快指针在X次走位后与慢指针相遇，此时快指针和慢指针相差X步，每次走位，X-1。

//当快指针追上慢指针的时候，慢指针走了X步。（问：快指针可以一次走两步，三步吗？）



这里只有当X=0时，快慢指针相遇，说明存在环，否则在环里死循环走位。

当快指针一次走N（N>2）步时，在X！=N 或 N 的倍数的情况下，存在无法相遇死循环的可能。
bool hasCycle(struct ListNode *head) {
	ListNode* fast = head;
	ListNode* slow = head;
	while (fast && fast->next)
	{
		slow = slow->next;
		fast = fast->next->next;
		if (fast == slow)
		{
			return true;
		}
	}
	return false;
}

 

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。 否则，返回 false 。

 

进阶：

你能用 O(1)（即，常量）内存解决此问题吗？

 

示例 1：

输入：head = [3,2,0,-4], pos = 1

输出：true

解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0

输出：true

解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1

输出：false

解释：链表中没有环。

 

提示：

链表中节点的数目范围是 [0, 104]

-105 <= Node.val <= 105

pos 为 -1 或者链表中的一个 有效索引 。

空指针判断

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        if(head == null) return false;
        while(head.next!=null&&fast.next!=null){
            fast=fast.next.next;
            head = head.next;
            if(head == null||fast ==null) break;
            if(fast.val == head.val)
                return true;
        }
       return false; 
    }
}