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

2020年1月30日21:28:52算法 LeetCode评论31阅读模式

题目描述: 给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。 说明:不允许修改给定的链表。文章源自随机的未知-https://sjdwz.com/11116.html

分析

给出示意图: Leetcode 142题 环形链表 II(Linked List Cycle II) Java语言求解文章源自随机的未知-https://sjdwz.com/11116.html

对符号的一些说明:文章源自随机的未知-https://sjdwz.com/11116.html

Leetcode 142题 环形链表 II(Linked List Cycle II) Java语言求解文章源自随机的未知-https://sjdwz.com/11116.html

 公式演算: 很容易得到: 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)个环。文章源自随机的未知-https://sjdwz.com/11116.html

/**
 * 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即可。文章源自随机的未知-https://sjdwz.com/11116.html

欢迎关注

扫下方二维码即可关注: Leetcode 142题 环形链表 II(Linked List Cycle II) Java语言求解文章源自随机的未知-https://sjdwz.com/11116.html

文章源自随机的未知-https://sjdwz.com/11116.html
欢迎关注本站微信公众号:随机的未知 如果喜欢本文,欢迎点赞,收藏,转发,打赏。
  • 本文由 发表于 2020年1月30日21:28:52
  • 转载请注明:来源:随机的未知 本文链接https://sjdwz.com/11116.html
算法

详解堆排序

什么是堆 堆首先是一个完全二叉树,堆分为大顶堆和小顶堆; 大顶堆 : 每个节点的值大于或等于其左右孩子节点的值,称为大顶堆。 小顶堆同理就是每个节点的值小于或等于其左右孩子节点的值。 注意: 每个节点...
算法

详解基数排序

基本思想 基数排序的思想是将整数按位数切割成不同的数字,然后按每个位数分别比较从而得到有序的序列。 例子 本文以数组中元素均为正整数来演示思想。 给定一个数组 arr = < 6, 56, 89 , ...
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定