题目:
给你一个链表的头节点 head ,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ,则返回 true 。 否则,返回 false 。
哈希表法
思路: 遍历单链表中的某个节点,将遍历到的每个节点在hashSet中是否存在,若不存在,就将该节点加入到hashSet中,若在hashSet中找见正在遍历的节点,就说明该单链表有环。
public class Solution {
public boolean hasCycle(ListNode head) {
Set<ListNode> set = new HashSet<>();
while(head != null) {
if (set.contains(head)) {
return true;
} else {
set.add(head);
}
head = head.next;
}
return false;
}
}
时间复杂度O(N),空间复杂度O(N)
快慢指针
思路: 从头节点开始,快指针一次走两步,慢指针一次走一步,若链表有环,则快慢指针一定会相遇。若快慢指针不相遇,说明没环。
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null || head.next.next == null) {
return false;
}
ListNode low = head.next;
ListNode fast = head.next.next;
while(low != fast) {
if (fast.next == null || fast.next.next == null) {
return false;
}
low = low.next;
fast = fast.next.next;
}
return true;
}
}
时间复杂度O(N), 空间复杂度O(1)
思考: 若需要返回入环的第一个节点,该怎么做。
哈希表法
思路: 遍历单链表中的某个节点,将遍历到的每个节点在hashSet中是否存在,若不存在,就将该节点加入到hashSet中,否则,第一次在hashSet中找见的节点即为第一个入环的节点。
public class Solution {
public ListNode hasCycle(ListNode head) {
Set<ListNode> set = new HashSet<>();
while(head != null) {
if (set.contains(head)) {
return head;
} else {
set.add(head);
}
head = head.next;
}
return null;
}
}
时间复杂度O(N),空间复杂度O(N)
快慢指针
思路: 从头节点开始,快指针一次走两步,慢指针一次走一步,若链表有环,则快慢指针一定会在环上的某个节点相遇,之后,快指针回到开头变成一次走一步,慢指针在原地开始继续一次走一步,再次相遇的节点一定在入环的第一个节点处。
public class Solution {
public ListNode hasCycle(ListNode head) {
if (head == null || head.next == null || head.next.next == null) {
return null;
}
ListNode low = head.next;
ListNode fast = head.next.next;
while(low != fast) {
if (fast.next == null || fast.next.next == null) {
return null;
}
low = low.next;
fast = fast.next.next;
}
fast = head;
while (low != fast) {
low = low.next;
fast = fast.next;
}
return low;
}
}
时间复杂度O(N), 空间复杂度O(1)
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)