LeetCode142之环形链表II

一、题目

请输入图片描述

二、一种解题思路

①方法介绍一:龟兔赛跑法升级版

    方法解析:①使用龟兔赛跑法先判断当前链表是否存在环(快慢指针能够相遇,则存在环)
                      ②假设链表头部到环起点的距离为x,环的长度为y,快指针每次走两步,慢指针每次走一步,

                        慢指针走t步后与快指针相遇,相遇的位置是(t - x)%y + x=(2*t - x)%y + x,求得t%y = 0
                        也就是说t是y的整数倍,故从链表头部和相遇的位置一起走x步会重新相遇。

   时间复杂度:O(n)

   空间复杂度:O(n)

②核心代码:

/**
     * 查找环形链表的入环节点
     * 方法: ①使用龟兔赛跑法先判断当前链表是否存在环(快慢指针能够相遇,则存在环)
     * ②假设链表头部到环起点的距离为x,环的长度为y,快指针每次走两步,慢指针每次走一步,
     * 慢指针走t步后与快指针相遇,
     * 相遇的位置是(t - x)%y + x=(2*t - x)%y + x,求得t%y = 0
     * 也就是t是y的整数倍,故从链表头部和相遇的位置一起走x步会重新相遇。
     *
     * @param head 头节点
     * @return 环形链表的入环节点
     */
    public static ListNode detectCycle1(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        ListNode target1 = head;
        ListNode target2 = head;
        while (target1 != null && target2 != null) {
            target1 = target1.next;
            if (target2.next != null) {
                target2 = target2.next.next;
            } else {
                target2 = target2.next;
            }
            if (target1 == target2) {
                break;
            }
        }
        if (target1 == target2) {
            target1 = head;
            while (target1 != target2) {
                target1 = target1.next;
                target2 = target2.next;
            }
            return target1;
        }
        return null;
    }

③辅助类

public class ListNode {
    public int val;
    public ListNode next;
 
    public ListNode(int x) {
        val = x;
        next = null;
    }
 
    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + val + "}";
    }
}

三、LeetCode成功截图
请输入图片描述

四、感想

加油,加油,再加油,坚持,坚持,再坚持。

Last modification:October 24th, 2019 at 12:49 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment