Follow up:
Can you solve it without using extra space?
Solution:
Using a fast pointer that advances two nodes each time and a slow pointer that advances on node, we always detect a cycle as the fast pointer cannot overtake the slow one without being in the same node in one of the ``turns"./** * 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) { ListNode fast = head; ListNode slow = head; while(fast!=null && fast.next !=null) { fast = fast.next.next; slow = slow.next; if(fast == slow) return true; } return false; } }
No comments :
Post a Comment