LeetCode141之环形链表(Java实现)

一、题目

请输入图片描述

 

二、两种解题思路及代码实现

 ①龟兔赛跑解法,快指针跳两个,慢指针跳一个,若两指针遇到一样,则有环

       时间复杂度:O(n)

       空间复杂度:O(1)

/**
 * 龟兔赛跑解法 ---- 李小豪
 * @param head
 * @return
 */
public boolean hasCycle1(ListNode head) {
    ListNode target1 = head;
    ListNode target2 = head;
    if (target1==null||target1.next == null || target1.next.next == null) {
        return Boolean.FALSE;
    }
    while (target2.next != target1.next.next) {
        target1 = target1.next.next;
        target2 = target2.next;
        if ( target1.next == null || target1.next.next == null) {
            return Boolean.FALSE;
        }
    }
    return Boolean.TRUE;
}

 ②使用Set将走过的节点保存起来,同时判断是否存在走过相同节点,若存在则为环

       时间复杂度:O(n)

       空间复杂度:O(n)

/**
 * 中间Set解法 ---- 李小豪
 * @param head
 * @return
 */
public boolean hasCycle2(ListNode head) {
    Set<ListNode> listNodes=new LinkedHashSet<>();
    ListNode target=head;
    while(target.next!=null){
        if(listNodes.contains(target)){
            return Boolean.TRUE;
        }
        listNodes.add(target);
        target=target.next;
    }
    return Boolean.FALSE;
}

三、基础类

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int x) {
        val = x;
        next = null;
    }
}
 

四、成功截图
请输入图片描述

测试结果还行

五、个人目标

接下来几个月将以前多学的Leetcode的题目在刷一遍,算法再学一遍,加油,每天升一级,愿未来努力继续。
2LeetCode141之环形链表(Java实现)

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

Leave a Comment