本文共 1021 字，大约阅读时间需要 3 分钟。
| 1 2 | 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. |
题意：不破坏原链表的情况下判断有没有环，，，，，，
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | /** * 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) { /不让修改原来的结构。本来还想用断链法. if (head== null || head.next== null ||head.next.next== null ) return null ; ListNode fast=head.next.next; ListNode slow=head.next; ///判断有没有环。找到相遇点 while (fast!=slow){ if (fast.next!= null && fast.next.next!= null ){ fast=fast.next.next; slow=slow.next; } else { return null ; } } fast=head; while (fast!=slow){ fast=fast.next; slow=slow.next; } return fast; } } |
PS：依然是快慢指针。先让fast走两步和slow走一步，判断有没有环先，有环的话就会相遇。当他们相遇后，让fast回到头，此时走一步。直到和slow相遇。则此时的相遇点位环入口！！！！！详情见
里面有一段推导
本文转自 努力的C 51CTO博客，原文链接:http://blog.51cto.com/fulin0532/1905477
转载地址：http://fykja.baihongyu.com/