你的位置:首页 > Java教程

[Java教程][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?

 

     关于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;  }}