LeetCode第141题:验证链表是否有环
题目描述
给定一个链表,判断链表中是否有环。
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
解法一
1.将链表节点的值放入set集合中(无序且不重复);
2.遍历链表直到head为null或发现有环
3.set中存在返回true,不存在add进去
public boolean hasCycle(ListCode head) {
Set<ListCode> node = new HashSet<>();
while(head != null) {
if(node.contains(head)) {
return true;
}else {
node.add(head);
}
head = head.next;
}
return false;
}
解法二
追及问题思路:“在操场跑圈,一起开始,我比你快,必追上你”
两个指针,一个一次跨一个节点,一个一次跨两个节点
public boolean hasCycle(ListNode head) {
if(head == null || head.next == null) return false;
ListNode slow = head.next;
ListNode fast = head.next.next;
while(slow != fast) {
if(fast == null || fast.next == null) return false;
slow = slow.next;
fast = fast.next.next;
}
return true;
}
来柯
发布了5 篇原创文章 · 获赞 0 · 访问量 27
私信
关注