1. 题目描述
题目链接：环形链表II
2. 题目分析
- 题目在上一个环形链表上让你证明有环无环，进而让你求此环点
- 首先，我们想想，在上一题中，我们快指针走2步，慢指针走一步，也就是
- 快指针 = 2 * 慢指针
- 快指针比慢指针多走了nb，最后交汇在环中的某一点
- 由上述式子相减
- 慢指针走的步数 = nb
- 所以，我们考虑考虑，我们怎么才能让慢指针走到环点呢？
- 当慢指针走a+nb时，是不是就走到环点了
- 所以，我们只需要再让慢指针走a步，也就是从头再定义一个指针，当两指针相交时，此节点就是该环点
- 或者利用Map大法，第一个重复的结点就是环点（不过，大概率不能过面试）
3. 题目代码
/** * 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){ return null; } boolean f = false; ListNode p1 = head; ListNode p2 = head; while(p2.next != null && p2.next.next != null){ p1 = p1.next; p2 = p2.next.next; if(p1 == p2){ f = true; break; } } if(f){ ListNode p3 = head; while(p3 != p1){ p3 = p3.next; p1 = p1.next; } return p1; }else{ return null; } } }
