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; } } }