141.环形链表

链接：141.环形链表
难度：Easy
标签：哈希表、链表、双指针
简介：给定一个链表，判断链表中是否有环。

题解 1 - java

• 编辑时间：2020-02-13
• 内存消耗：47MB
• 编程语言：java
• 解法介绍：使用快慢指针，若快指针与慢指针指向一个节点则存在。

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null)
			return false;
		ListNode slow = head;
		ListNode fast = head.next;
		while (fast != null && fast.next != null) {
			if (slow == fast)
				return true;
			slow = slow.next;
			fast = fast.next.next;
		}
		return false;
    }
}

题解 2 - typescript

• 编辑时间：2020-10-09
• 执行用时：96ms
• 内存消耗：40MB
• 编程语言：typescript
• 解法介绍：双指针。

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

题解 3 - typescript

• 编辑时间：2021-03-06
• 执行用时：92ms
• 内存消耗：40.4MB
• 编程语言：typescript
• 解法介绍：快慢指针。

function hasCycle(head: ListNode | null): boolean {
  if (head === null || head.next === null) return false;
  let fast: ListNode | null = head.next;
  let slow: ListNode | null = head;
  while (fast !== slow && fast !== null && fast.next !== null) {
    fast = fast.next.next;
    slow = slow!.next;
  }
  return fast === slow;
}

题解 4 - c

• 编辑时间：2021-11-19
• 执行用时：12ms
• 内存消耗：7.7MB
• 编程语言：c
• 解法介绍：快慢指针。

bool hasCycle(struct ListNode *head) {
    if(!head) return 0;
    struct ListNode *slow = head;
    struct ListNode *fast = head->next;
    while (fast && fast->next && fast != slow) fast = fast->next->next, slow = slow->next;
    return fast == slow;
}

题解 5 - cpp

• 编辑时间：2022-03-03
• 执行用时：8ms
• 内存消耗：8MB
• 编程语言：cpp
• 解法介绍：双指针。

class Solution {
   public:
    bool hasCycle(ListNode *head) {
        if (!head) return false;
        ListNode *fast = head->next, *slow = head;
        while (fast && fast->next && fast != slow) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return fast && fast->next;
    }
};

题解 6 - cpp

• 编辑时间：2023-07-29
• 执行用时：8ms
• 内存消耗：8MB
• 编程语言：cpp
• 解法介绍：快慢指针。

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (!head) return false;
        ListNode *slow = head, *fast = head;
        while (fast && fast->next && fast->next != slow) {
            fast = fast->next->next;
            slow = slow->next;
        }
        return fast && fast->next == slow;
    }
};

题解 7 - python

• 编辑时间：2023-07-29
• 执行用时：64ms
• 内存消耗：20.2MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if not head:
            return False
        slow = fast = head
        while fast and fast.next and fast.next != slow:
            fast = fast.next.next
            slow = slow.next
        return fast and fast.next == slow