141.环形列表

给定一个链表，判断链表中是否有环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环

image

经过这个题，学习到了哈希表和快慢指针的两种解法

哈希表（效率低）

class Solution {
    public boolean hasCycle(ListNode head)
    {
        HashSet<ListNode> hashSet = new HashSet<>();
        while (head!=null) {
            if (hashSet.contains(head))
            {
                return true;
            }
            hashSet.add(head);
            head = head.next;
        }
return false;
    }
}

由于哈希表的特点，所以把经过的Node节点存入哈希表。随着链表的遍历，如果它有环，在hashSet.contains(head)判断时.发现这个节点之前已经存入了哈希表。return ture.时间复杂度是O(n) ,空间复杂度是O(n).

image

快慢指针（效率比哈希表高）

class Solution {
    public boolean hasCycle(ListNode head)
    {     
      if(head!=null&&head.next==null)
        {  return false;}       
        ListNode q= head; //这是快指针
        while (q!=null)
        {
            if (q.next==null)
            {return false;}
            head = head.next;//head 是慢指针 一次走一个
            q = q.next.next;//  q 是快指针，一次走两个
            if (q==head) { return true;}   
           }
       return  false;
    }
}

查看别人的题解时，学习到了快慢指针的做法，简单来说，就是一快一慢两个指针遍历链表，如果链表有环，经过一段时间后快慢指针一定会重合。 时间复杂度是O(n) ,空间复杂度是O(1).

image