LeetCode141之环形链表(Java实现)

环形链表(Java实现)"/>

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的题目在刷一遍，算法再学一遍，加油，每天升一级，愿未来努力继续。