[LeetCode] Linked List Cycle

王朝学院·作者佚名  2016-05-27
窄屏简体版  字體: 小  |  中  |  大  |  超大  

[LeetCode] Linked List CycleGiven a linked list, determine if it has a cycle in it.

Follow up:Can you solve it without using extra space?

关于cycle,第一个想法自然就是用hashmap来做。注意用hashmap.put()method的时候,value随便设置一个数就可以了。

因为我们只是检测key是否有重复的,value在这里的意义不大。

代码如下。~

/** * 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) { HashMap<ListNode,Integer> hash=new HashMap<ListNode,Integer>(); if(head==null){ return false; } while(head!=null){ if(hash.containsKey(head)){ return true; } hash.put(head,1); head=head.next; } return false; }}

但是再看一下follow up那里要求的是without extra space,那么这样的话hashmap就暂时不能用了。

用two pointer来做就可以了。快慢指针。(fase/slow) (fast每次走两步,slow则是一步。)

如果有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) { if(head==null||head.next==null){ return false; } ListNode fast=head; ListNode slow=head; while(fast!=null&&fast.next!=null){ slow=slow.next; fast=fast.next.next; if(slow==fast){ return true; } } return false; }}

 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
© 2005- 王朝網路 版權所有 導航