Leetcode 142题 环形链表 II（Linked List Cycle II） Java语言求解

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Leetcode 142题 环形链表 II（Linked List Cycle II） Java语言求解，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1822字，纯文字阅读大概需要3分钟。

内容图文

题目描述：
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
说明：不允许修改给定的链表。

分析

给出示意图：

对符号的一些说明：

公式演算：
很容易得到：
m=x+y（环的长度两种表示形式）;
快指针走两步，慢指针走一步。所以快指针的速度是慢指针的速度的二倍，所以相同时间内，快指针走的长度也是慢指针走的长度的二倍：
有： f=2s;
在快指针走过 圈后两指针相遇，有: m+kn+y=2(m+y);
去括号后有： m+kn=2m+y;
解得： m=kn-y;
又因为:n=x+y;
所以有：m=kn-(n-x);
所以：m=x+n(k-1)。
m是头节点到环起点的长度；
x是相遇点到头节点的长度；
x-m是(k-1)个环的长度。
通过公式的演算，我们能够明白：
找到相遇点后，链表头节点与相遇点节点同时出发，相遇处便是环的起点。相遇点节点多走了(k-1)个环。

/**
 * 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;
        ListNode slow = head;
        ListNode fast = head;

        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){
                break;
            }
        }
        if(fast == null || fast.next == null)
            return null;
        fast = head;
        while(slow != fast){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

对代码的解释：
1、如果head是空，则不存在环，直接返回null；
2、设置快慢指针开始均指向head，设置循环条件，快指针不为空且快指针的next域指向的不为空进入循环，其中空指针的next域的指向不为空保证快指针可以走两步，否则有可能出现空指针异常；
3、如果快慢指针指向相同节点，则break掉，是相遇点；
4、第一次循环过后，如果fast为空或者fast.next为空，则不存在环，返回null；
5、如果存在环，让fast指针从开始移动，slow指针从相遇点移动，相遇则为起点，将其return即可。

欢迎关注

扫下方二维码即可关注:

内容总结

以上是互联网集市为您收集整理的Leetcode 142题 环形链表 II（Linked List Cycle II） Java语言求解全部内容，希望文章能够帮你解决Leetcode 142题 环形链表 II（Linked List Cycle II） Java语言求解所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端