【腾讯】环形链表(证明环的位置)

末蓝、 2022-11-28 13:29 141阅读 0赞

# 1. 题目描述 #

题目链接：[环形链表II][II]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70_pic_center]

# 2. 题目分析 #

1.  题目在上一个环形链表上让你证明有环无环，进而让你求此环点
2.  首先，我们想想，在上一题中，我们快指针走2步，慢指针走一步，也就是

*  **快指针 = 2 \* 慢指针**
 *  **快指针比慢指针多走了nb**，最后交汇在环中的某一点
 *  由上述式子相减
 *  **慢指针走的步数 = nb**
 *  所以，我们考虑考虑，我们怎么才能让慢指针走到环点呢？
 *  当**慢指针走a+nb**时，是不是就走到环点了
 *  所以，我们只需要再让慢指针走a步，也就是从头再定义一个指针，当两指针相交时，此节点就是该环点

1.  或者利用Map大法，第一个重复的结点就是环点（不过，大概率不能过面试）  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70_pic_center 1]

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

[II]: https://leetcode-cn.com/problems/linked-list-cycle-ii/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/def4def2b31d4505bc3b9865bcc544d3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221124/032d7a55d6394a4e9653115ab53fd152.png