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 }