leetcode142、141. 判断环形链表和求出环形链表的第一个入环的结点(java实现）

柔光的暖阳◎ 2022-02-12 11:25 79阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDA1NjY2_size_16_color_FFFFFF_t_70]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDA1NjY2_size_16_color_FFFFFF_t_70 1]

# 问题分析：首先判断链表是否有环： #

**这道题就类似于现实生活中的赛跑问题，我们跑步的时候，有的人跑的慢，有的人或许跑的快。我们随机给两个人指定一个跑步路线，让两个人同时从起始点出发，如果在某一时刻，速度快的人追上了慢的人，那么就说明这个中间可能路线是一个环形的。**  
**！！！ 注意，假设我们跑的慢的人的速度是v，跑的快的人的速度是2v，那么跑的快的人追上跑的慢的人的位置不一定是入环的结点！这得分情况。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDA1NjY2_size_16_color_FFFFFF_t_70 2]

**如果是下面这种环呢？**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDA1NjY2_size_16_color_FFFFFF_t_70 3]

## 显而易见，他们的第一次相遇位置就不是入环的结点了。我们对这种环进行分析。让slow的速度等于V,fast等于2V。![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDA1NjY2_size_16_color_FFFFFF_t_70 4] ##

## 判断是否有环代码 ##

/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */
    public class Solution { 
        public boolean hasCycle(ListNode head) { 
            if(head==null||head.next==null){ 
                return false;
            }
            ListNode fast=head;
            ListNode slow=head;
            while(fast!=null&&fast.next!=null){ 
                fast=fast.next.next;
                slow=slow.next;
                if(fast==slow){ 
                    return true;
                }
            }
            return false;
        }
    }

### 判断入环的第一个结点。 ###

/** * 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){ 
                return null;
            }
            ListNode fast=head;
            ListNode slow=head;
            while(fast!=null&&fast.next!=null){ //判断环
                fast=fast.next.next;
                slow=slow.next;
                if(slow==fast){ 
                    slow=head;
            while(slow!=fast){ //判断第一个入环结点
                fast=fast.next;
                slow=slow.next;
            }
            return slow;
                }
            }
            return null;
        }
    }

![在这里插入图片描述][20190428200400507.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDA1NjY2_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190428192051957.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDA1NjY2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDA1NjY2_size_16_color_FFFFFF_t_70 1]: /images/20220212/6124672d524c43bbb189e27b5dba70f5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDA1NjY2_size_16_color_FFFFFF_t_70 2]: /images/20220212/7315176332954e76ad677a8c94ce3662.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDA1NjY2_size_16_color_FFFFFF_t_70 3]: /images/20220212/4d345692f4684267a528d4e787c1d3ac.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDA1NjY2_size_16_color_FFFFFF_t_70 4]: /images/20220212/934890cc274d44e095566db05e068468.png
[20190428200400507.png]: /images/20220212/7b4b5afa21fb4d508e29573304f28ead.png