null
.
Follow up:
Can you solve it without using extra space?
Solution:
We first detect if a cycle exists, as Linked List Cycle I. Then we keep a pointer in the same position and obtain the length of the loop. With that we just have to keep the fast pointer this amount of positions in advance and they will always cross where the cycle starts./** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode detectCycle(ListNode head) { int states = 0; if (head == null || head.next == null) return null; ListNode slowPointer = head; ListNode fastPointer = head.next; while(fastPointer!=null && fastPointer.next != null && fastPointer!=slowPointer) { fastPointer = fastPointer.next.next; slowPointer = slowPointer.next; } if (fastPointer != slowPointer) return null; int counter = 1; fastPointer = fastPointer.next; while(fastPointer!=slowPointer) { fastPointer = fastPointer.next; counter++; } fastPointer = head; for (int i=0; i< counter; i++) fastPointer = fastPointer.next; slowPointer = head; while(fastPointer!=slowPointer) { fastPointer = fastPointer.next; slowPointer = slowPointer.next; } return fastPointer; } }
No comments :
Post a Comment