leetcode141-环形链表

原题

给定一个链表,判断链表中是否有环。

为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。

示例1:

输入: head = [3,2,0,-4], pos = 1
输出: true
解释: 链表中有一个环,其尾部连接到第二个节点。

leetcode141-环形链表

示例2:

输入: head = [1,2], pos = 0
输出: true
解释: 链表中有一个环,其尾部连接到第一个节点。

leetcode141-环形链表

示例3:

输入: head = [1], pos = -1
输出: false
解释: 链表中没有环。

leetcode141-环形链表

进阶:

你能用 O(1)(即,常量)内存解决此问题吗?

解法

思想

  1. HashSet
    依次将获取到的链表元素插入一个HashSet中,看是否有相同元素。
  2. 双指针
    一个快指针一个慢指针,如果有环快指针总会赶上慢指针。

代码

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) {
        if(head == null) return false;
        Set<ListNode> set = new HashSet<>();
        ListNode cur = head;
        while(cur.next!=null){
            if(set.contains(cur)) return true;
            set.add(cur);
            cur = cur.next;
        }
        return false;
    }
}

双指针:

/**
 * 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) {
         if(head == null){
            return false;
        }
        ListNode slow = head;
        ListNode fast = head;

        while (slow!=null && fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){
                return true;
            }
        }
        return false;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode141-%e7%8e%af%e5%bd%a2%e9%93%be%e8%a1%a8/

(0)
彭晨涛彭晨涛管理者
上一篇 2019年12月13日 18:05
下一篇 2019年12月15日

相关推荐

  • leetcode836-矩形重叠

    原题 矩形以列表 [x1, y1, x2, y2] 的形式表示,其中 (x1, y1) 为左下角的坐标,(x2, y2) 是右上角的坐标。 如果相交的面积为正,则称两矩形重叠。需要…

    算法 2020年3月18日
    0450
  • leetcode543-二叉树的直径

    原题 给定一棵二叉树,你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。 示例: 给定二叉树 1 / \ 2 3 / \ 4 5…

    算法 2020年3月10日
    0210
  • leetcode68-文本左右对齐

    原题 https://leetcode.cn/problems/text-justification/description 解法 贪心即可 func fullJustify(wo…

    算法 2024年3月23日
    080
  • leetcode18-四数之和

    原题 给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + c + d 的值与 ta…

    算法 2020年5月5日
    0120
  • leetcode200-岛屿数量

    原题 给定一个由 '1'(陆地)和 '0'(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水…

    算法 2019年11月24日
    0150
  • leetcode66-加一

    原题 给定一个由整数组成的非空数组所表示的非负整数,在该数的基础上加一。 最高位数字存放在数组的首位, 数组中每个元素只存储单个数字。 你可以假设除了整数 0 之外,这个整数不会以…

    算法 2019年11月14日
    0140
  • leetcode67-二进制求和

    原题 给定两个二进制字符串,返回他们的和(用二进制表示)。 输入为非空字符串且只包含数字 1 和 0。 示例 1: 输入: a = “11”, b = “1” 输出: “100” …

    算法 2019年11月15日
    0100
  • leetcode124-二叉树中的最大路径和

    原题 给定一个非空二叉树,返回其最大路径和。 本题中,路径被定义为一条从树中任意节点出发,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。 示例 1: 输入: [1…

    算法 2020年4月26日
    0170
  • leetcode454-四数相加II

    原题 给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ,使得 A[i] + B[j] + C[k] + D[l] = 0。 为…

    算法 2019年12月27日
    070
  • 剑指offer64-求1+2+…+n

    原题(来源Leetcode) 求 1+2+...+n ,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)。 示例1…

    算法 2020年6月2日
    0550

发表回复

登录后才能评论