1. Title
Linked List Cycle II
2. Http address
https://leetcode.com/problems/linked-list-cycle-ii/
3. The question
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Note: Do not modify the linked list.
Follow up:
Can you solve it without using extra space?4. My code(AC)
-
1 // Accepted 2 public static ListNode detectCycle(ListNode head) { 3 4 if( head == null) 5 return null; 6 ListNode last ,pre; 7 last = head; 8 pre = head.next; 9 10 if( pre == last)11 return head;12 while( pre != null)13 {14 if( pre == last)15 {16 break;17 }18 last = last.next;19 pre = pre.next;20 if( pre != null)21 {22 pre = pre.next;23 }else{24 pre = null;25 }26 }27 28 if ( pre == null)29 {30 return null;31 }32 ListNode second = pre.next;33 ListNode first = head;34 pre.next = null;35 36 int lenA,lenB;37 38 ListNode p = first;39 lenA = 0 ;40 while( p != null)41 {42 lenA++;43 p = p.next;44 }45 lenB = 0 ;46 p = second;47 while( p != null)48 {49 lenB++;50 p = p.next;51 }52 53 if( lenA >= lenB)54 {55 int dis = lenA - lenB;56 while( dis > 0 && first != null)57 {58 first = first.next;59 dis--;60 }61 62 }else{63 int dis = lenB - lenA;64 while( dis > 0 && second != null)65 {66 second = second.next;67 dis--;68 }69 }70 71 while( first != null && second != null && first != second)72 {73 first = first.next;74 second = second.next;75 }76 return second;77 78 79 }