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



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


先判断链表是否相交，我们可以运用两个链表相交后就变成了一条链表这个特性来判断，因为如果两条链表相交，那么这两条链表的最后一个节点一定是同一个节点，否则不可能相交
	//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;
	}

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。 否则，返回 false 。
进阶：
你能用 O(1)（即，常量）内存解决此问题吗？
题解方法一：
hash表遍历所有节点，每次遍历到一个节点时，判断该节点此前是否被访问过。

复杂度分析

时间复杂度：O(N)，其中 N 是链表中的节点数。

空间复杂度：O(N)，其中 NN 是链表中的节点数。主要为哈希表的开销，最坏情况下我们需要将每个节点插入到哈希表中一次。
count()返回集合中某个值元素的个数
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        //使用hash表，遍历一次；
        unordered_set<ListNode*> visited;
        while(head!=NULL){
            if(visited.count(head)==1){
                return true;
            }
            visited.insert(head);
            head=head->next;
        }
        return false;
    }

    
   
};

题解方法二：使用快慢指针O(1)内存
快指针一次走两步，慢指针一次走一步，若无环，快指针永远在前面；若有环，一定会相遇;
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head==NULL||head->next==NULL) return false;
        ListNode *fast=head->next,*slow=head;
        while(fast!=slow){
            if(fast==NULL||fast->next==NULL) return false;
            fast=fast->next->next;
            slow=slow->next;
        }
        return true; 
    }
};

 

如果链表中有某个节点，可以通过连续跟踪 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; 
    }
}

 

 


 

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

如果链表中有某个节点，可以通过连续跟踪 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;
}