题解 | #判断链表中是否有环#

题目：判断链表中是否有环

描述：判断给定的链表中是否有环。如果有环则返回true，否则返回false。

你能给出空间复杂度的解法么？输入分为2部分，第一部分为链表，第二部分代表是否有环，然后回组成head头结点传入到函数里面。-1代表无环，其他的数字代表有环，这些参数解释仅仅是为了方便读者自测调试。

示例1：输入：{3,2,0,-4},1，返回值：true，说明：第一部分{3,2,0,-4}代表一个链表，第二部分的1表示，-4到位置1，即-4->2存在一个链接，组成传入的head为一个带环的链表,返回true。

解法一：

思路分析：判断链表当中是否存在环，我们可以使用指针判别法，定义两个指针的存在，将两个指针同时从链表的头部出发，一个指针一次走一个next的值，另一个指针走两个next，如果走的快的指针追上慢的指针，就说明该链表为环形链表；如果走的快的指针到了链表末尾也没有追上走的慢的指针，那么链表就不是环形链表。

举例图示：输入：{3,2,0,-4},1

题上说明，1代表-4到位置1存在着一个链表，所以我们得到这道题应该返回true。下面进行判断。

具体C语言程序如下所示：

#include<stdbool.h>
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

/**
 * 
 * @param head ListNode类 
 * @return bool布尔型
 */
bool hasCycle(struct ListNode* head ) {
    struct ListNode*p1 = head,*p2 = head;//定义两个指针
    while((p2 != NULL) && (p2->next != NULL) ){//停止条件
        p1 = p1->next;//走一步
        p2 = p2->next->next;//走两步
        if(p1 == p2){
            return 1;
        }
    }
    return 0;
}

假设链表的节点数量为n，则该算法的时间复杂度为O(n)。除两个指针外，没有使用任何额外的存储空间，所以空间复杂度是O(1)。

解法二：

思路分析：同样可以采用java来解决问题，首先创建一个HashSet集合，用来存储曾经遍历过的结点，通过从头节点开始，依次遍历链表当中的每一个结点，每次遍历一个结点就与HashSet集合当中存储的结点作比较，如果发现HashSet当中存在相同结点的序号，则说明链表当中有环，如果不存在相同序号，就把新节点存入HashSet集合当中，重复以上操作。

具体java程序如下所示：

import java.util.Set;
import java.util.HashSet;
/**
 * 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) {
        Set<ListNode> new1 = new HashSet<>();
        while(head != null){
            if(new1.contains(head))//如果一旦包含
                return true;
            new1.add(head);//否则将其添加进去
            head = head.next;//下一个
        }
        return false;
    }
}

假设从链表表头到刚开始的距离是D，链表的长度为S，则每一次HashSet查找元素的时间复杂度为O(1)，总体的时间复杂度为O(N)，空间复杂度为D+S-1，所以为O(N)。