【LeetCode】- Java - 环形链表

雨点打透心脏的1/2处 2022-01-26 10:07 179阅读 0赞

给定一个链表，判断链表中是否有环。

为了表示给定链表中的环，我们使用整数 `pos` 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 `pos` 是 `-1`，则在该链表中没有环。

**示例 1：**

输入：head = [3,2,0,-4], pos = 1
    输出：true
    解释：链表中有一个环，其尾部连接到第二个节点。

![20190528191031109.png][]

**示例 2：**

输入：head = [1,2], pos = 0
    输出：true
    解释：链表中有一个环，其尾部连接到第一个节点。

![20190528191046712.png][]

**示例 3：**

输入：head = [1], pos = -1
    输出：false
    解释：链表中没有环。

![20190528191057512.png][]

**进阶：**

你能用 *O(1)*（即，常量）内存解决此问题吗？

方法一：遍历链表，用一个HashSet记录，出现过的节点，当遇到相同节点时表示出现了环，当都没有出现时表示不存在环，此空间复杂度为O(N),我的代码如下：

public boolean hasCycle(ListNode head) {
    		ListNode pNode = head;
    		HashSet<ListNode> hSet = new HashSet<>();
    		while (pNode != null) {
    			if (hSet.contains(pNode)) {
    				return true;
    			} else {
    				hSet.add(pNode);
    			}
    			pNode = pNode.next;
    		}
    		return false;
    	}

方法二：使用快慢指针，空间复杂度O(1)，我的代码如下：

public boolean hasCycle(ListNode head) {
    		if (head == null) {
    			return false;
    		}
    		ListNode slow = head;
    		ListNode fast = head.next;
    		if (fast == null) {
    			return false;
    		}
    		// 快指针先动，判断是否相等
    		while (fast != null && fast.next != null) {
    			if (fast.next == slow) {
    				return true;
    			} else {
    				slow = slow.next;
    				fast = fast.next.next;
    			}
    		}
    		return false;
    	}

[20190528191031109.png]: /images/20220126/6682b85b5f6c48a2b0be8845eeec7761.png
[20190528191046712.png]: /images/20220126/1e00a6567a7847c2984811dccce6e54d.png
[20190528191057512.png]: /images/20220126/d3d2960c43c1437aa98995311ccf06aa.png