数学解决——环形链表问题

人生之路不会是一帆风顺的,我们会遇上顺境,也会遇上逆境,在所有成功路上折磨你的,背后都隐藏着激励你奋发向上的动机,人生没有如果,只有后果与结果,成熟,就是用微笑来面对一切小事。

导读:本篇文章讲解 数学解决——环形链表问题,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com,来源:原文

环形链表

数学解决——环形链表问题

 思路:

  1. 先通过快慢双指针去遍历链表,直到fast与slow相遇停止(fast的速度必须是slow速度的二倍,不能是三倍、四倍…试想如果环只有两个结点,fast肯定先进环,若后进环slow刚好与fast错开,slow走三倍,fast走两步,是永远不会相遇的!
  2. 再让一个指针从头节点遍历,另一个指针从上一次快慢指针相遇处遍历,两个指针的遍历速度一致必定会在循环的结点入口相遇,想不来?解释如下图:

数学解决——环形链表问题

 代码如下:

public class Solution {
    public ListNode detectCycle(ListNode head) {
                //快指针必须是慢指针速度的二倍
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                break;
            }
        }
        if(fast == null || fast.next == null){
            return null;
        }
        slow = head;
        while(slow != fast){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}

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

文章由半码博客整理,本文链接:https://www.bmabk.com/index.php/post/124364.html

(0)

相关推荐

发表回复

登录后才能评论
半码博客——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!