本文共 2596 字,大约阅读时间需要 8 分钟。
title: LeetCode中环形链表题解
description: LeetCode中环形链表题解-java tags:难度简单877收藏分享切换为英文接收动态反馈
给定一个链表,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 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
或者链表中的一个 有效索引 。定义两个指针,为快慢指针,慢指针一开始位于head,快指针位于head .next ,慢指针一次移动一步,快指针一次移动两步, 如果,在移动的过程中,快慢指针重合,说明该链表为环形链表,否则快指针到达链表尾部,该链表不为环形链表
/** * 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) { // 如果head为空,或者head.next为空,返回false if (head == null || head.next == null) { return false; } // 定义一个慢指针与快指针 ListNode slow = head; ListNode fast = head.next; // 如果快慢指针不相同,进入循环 while(slow != fast ){ // 如果快指针为空或,快指针的下一指针为空,则返回false if(fast == null || fast.next == null){ return false; // 如果不为空,则慢指针走一步,快指针走两步,进入下一循环判断 }else{ slow = slow.next; fast = fast.next.next; } } return true; }}
时间复杂度:O(N),其中 N 是链表中的节点数。
空间复杂度:O(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) { Setseen = new HashSet (); while (head != null) { if (!seen.add(head)) { return true; } head = head.next; } return false; }}
时间复杂度:O(N),其中 N 是链表中的节点数。最坏情况下我们需要遍历每个节点一次。
空间复杂度:O(N),其中 N 是链表中的节点数。主要为哈希表的开销,最坏情况下我们需要将每个节点插入到哈希表中一次。
turn false;
} }#### 复杂度分析- 时间复杂度:O(N),其中 N 是链表中的节点数。最坏情况下我们需要遍历每个节点一次。- 空间复杂度:O(N),其中 N 是链表中的节点数。主要为哈希表的开销,最坏情况下我们需要将每个节点插入到哈希表中一次。#### 提交详情![image-20201213190825567](https://img-blog.csdnimg.cn/img_convert/2af2a9c88f669c3e32a1910939845c2f.png)
转载地址:http://dkwzi.baihongyu.com/