Leetcode-Linked List Cycle II

 1 /**
 2  * Definition for singly-linked list.
 3  * class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int x) {
 7  *         val = x;
 8  *         next = null;
 9  *     }
10  * }
11  */
12 public class Solution {
13     public ListNode detectCycle(ListNode head) {
14         if (head==null || head.next==null) return null;
15 
16         ListNode preHead = new ListNode(0);
17         preHead.next = head;
18         ListNode p1 = head, p2=head, end=preHead;
19         boolean hasRing = false;
20         while (p1!=null && p2!=null){
21             end = p1;
22             p1=p1.next;
23             if (p2.next!=null) p2 = p2.next.next;
24             else break;
25                 
26             if (p1==p2){
27                 hasRing=true;
28                 break;
29             }
30         }
31 
32         if (!hasRing) return null;
33         end = p2;
34         ListNode head2 = p2.next;
35         end.next=null;
36 
37  
38         p1 = head;
39         int len1=1;        
40         while (p1.next!=null){
41             p1 = p1.next;
42             len1++;
43         }
44 
45         p2 = head2;
46         int len2=1;
47         while (p2.next!=null){
48             p2 = p2.next;
49             len2++;
50         }     
51         
52         if (len1>len2){
53             while (len1!=len2){
54                 head = head.next;
55                 len1--;
56             }
57         } else if (len1<len2)
58             while (len1!=len2){
59                 head2 = head2.next;
60                 len2--;
61             }
62 
63         p1 = head;
64         p2 = head2;
65 
66         while (p1!=p2){
67             p1 = p1.next;
68             p2 = p2.next;
69         }
70 
71         return p1;
72         
73     }
74 }