LeetCode141之环形链表(Java实现)

野性酷女 2022-05-12 15:22 156阅读 0赞

一、题目

![70][]

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

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

时间复杂度：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;
        }
    }

四、成功截图

![70 1][]

测试结果还行

五、个人目标

接下来几个月将以前多学的Leetcode的题目在刷一遍，算法再学一遍，加油，每天升一级，愿未来努力继续。

[70]: /images/20220504/8440a36cde3744008fb5a111ab4e9d2f.png
[70 1]: /images/20220504/24cdc57d06df44f69719a27aeb7fdf2f.png