首页 > 代码库 > 141. Linked List Cycle
141. Linked List Cycle
Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
Solution1:
思路：有cycle：1.循环退不出来2.有个节点被指两次。分析清楚了就很简单，用hashset记录每个节点，如果碰到重复节点就是cycle，没有节点就会最终退出循环。
/** * 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) { Set<ListNode> res=new HashSet<ListNode>(); if(head==null) { return false; } ListNode slow=head; while(slow!=null) { if(!res.contains(slow)) { res.add(slow); } else { return true; } slow=slow.next; } return false; }}
Solution2:
dicussion中O(1)解法：快慢指针。如果有cycle，那么快慢指针肯定会相遇，如果没有cycle最终快慢指针不同。
public class Solution { public boolean hasCycle(ListNode head) { if(head == null || head.next == null) return false; ListNode slow = head; ListNode fast = head.next; while(fast != null && fast != slow && fast.next != null){ slow = slow.next; fast = fast.next.next; } if(fast == slow) return true; return false; }}
141. Linked List Cycle
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。