首页 > 代码库 > Leetcode Linked List Cycle
Leetcode 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?
这道题用来判断链表中是否有循环，最开始我想的是遍历链表，同时用一个list保存遍历过的节点，然后查看该节点的next节点是否存在于list中，若存在则说明该链表存在循环。
但由于是n2的时间代价，提示我超时间。
1 package Linked.List.Cycle; 2 3 import java.util.ArrayList; 4 import java.util.List; 5 6 public class LinkedListCycle { 7 public boolean hasCycle(ListNode head) { 8 int len=0; 9 List<ListNode> list=new ArrayList<ListNode>();10 ListNode index=head; 11 if(index==null) return false;12 if(index.next==index) return true;13 boolean isCycle=false;14 while(index!=null){15 list.add(index);16 ListNode obj=index.next;17 if(list.contains(obj))18 {19 isCycle=true;20 break;21 }22 index=index.next;23 }24 if(isCycle)25 return true;26 else return false;27 28 }29 }
后来查看人家的算法思想，发现快慢指针在链表中是个很好用的工具，不仅可以轻松得到中间节点，还可以解决相遇问题
1 package Linked.List.Cycle; 2 3 public class LinkedListCycle1 { 4 public boolean hasCycle(ListNode head) { 5 ListNode fast=head; 6 ListNode slow=head; 7 boolean isCycle=false; 8 ListNode index=head; 9 if(index==null) return false;10 if(index.next==index) return true;11 if(index.next.next==index) return true;12 if(index.next==null) return false;13 while(fast!=null&&fast.next!=null){14 slow=slow.next;15 fast=fast.next.next;16 if(slow==fast)17 {18 return true;19 }20 }21 return false;22 }23 }
Leetcode Linked List Cycle
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。