BAT面试算法进阶(11)- 最长的斐波那契子序列的长度(动态规划法)
BAT面试算法进阶(10)- 最长的斐波那契子序列的长度(暴力法)
BAT面试算法进阶(8)- 删除排序数组中的重复项
BAT面试算法进阶(7)- 反转整数
BAT面试算法进阶(6)- BAT面试算法进阶(6)-最长回文子串(方法二)
BAT面试算法进阶(5)- BAT面试算法进阶(5)- 最长回文子串(方法一)
BAT面试算法进阶(4)- 无重复字符的最长子串(滑动法优化+ASCII码法)
BAT面试算法进阶(3)- 无重复字符的最长子串(滑动窗口法)
BAT面试算法进阶(2)- 无重复字符的最长子串(暴力法)
BAT面试算法进阶(1)--两数之和

一.面试题目

给定一个链表,判断链表中是否有环.
难度升级: 试试能否在不使用额外空间解决此问题?

二.解决方案(哈希表)

思路

我们可以通过检查一个结点此前是否被访问过来判断链表是否为环形链表.常用方法,一般是使用哈希表.

算法

我们遍历所有的节点并在哈希表中存储每个结点的引用(或内存地址).如果当前节点为空结点null,表示我们已经检测到链表的末尾的下一个节点.那么表示我们已经完成了链表的遍历,并且此链表不是环形链表.如果当前结点的引用已经存在过哈希表中,那么即可立马返回true(表示此链表为环形链表).

三.代码

Java Code

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

四.复杂度分析

• 时间复杂度: O(n),对于含有n个元素的链表,我们访问每个元素最多一次.添加一个结点到哈希表中只需要花费O(1)的时间.
• 空间复杂度:O(n),空间取决于添加哈希表中的元素数目.最多可以添加n个元素.

五.学习建议

• 只要明白哈希表,即可解决这个问题.!