141. Linked List Cycle

🟢   🔖  哈希表 链表 双指针  🔗 LeetCode

题目

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Example 1:

Input: head = [3,2,0,-4], pos = 1

Output: true

Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:

Input: head = [1,2], pos = 0

Output: true

Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Example 3:

Input: head = [1], pos = -1

Output: false

Explanation: There is no cycle in the linked list.

Constraints:

• The number of the nodes in the list is in the range [0, 104].
• -10^5 <= Node.val <= 10^5
• pos is -1 or a valid index in the linked-list.

Follow up: Can you solve it using O(1) (i.e. constant) memory?

题目大意

判断链表是否有环，不能使用额外的空间。

解题思路

• 思路一：哈希表
  • 最简单的思路是遍历所有节点，每次遍历节点之前，使用哈希表判断该节点是否被访问过；
  • 如果访问过就说明存在环；
  • 如果没访问过则将该节点添加到哈希表中，继续遍历判断；
• 思路二：快慢指针
  • 两个指针从同一位置同时出发，一快一慢，如果有环，那么快的一方总能追上慢的一方；
  • 慢指针每次前进一步，快指针每次前进 n 步（n >= 2）；
  • 如果两个指针在链表头节点以外的某一节点相遇了，那么说明链表有环；
  • 否则，如果（快指针）到达了某个没有后继指针的节点时，那么说明没环；

代码

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function (head) {
	let slow = head;
	let fast = head;
	while (fast && fast.next) {
		slow = slow.next;
		fast = fast.next.next;
		if (fast == slow) return true;
	}
	return false;
};

相关题目

相关题目

• 142. 环形链表 II
• 202. 快乐数

- [142. 环形链表 II](https://leetcode.com/problems/linked-list-cycle-ii)
- [202. 快乐数](https://leetcode.com/problems/happy-number)