141.环形链表
#leetcode#链表#双指针#hash表 2025-01-26

Problem: 141. 环形链表

思路

hash表不用多说。
重点说下快慢指针，当双指针都进入环中，循环下来fast必定和slow碰面，这保证了正确性

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//! 快慢指针 n,1
class Solution {
 public:
  bool hasCycle(ListNode *head) {
    if (head == nullptr) {
      return false;
    }
    ListNode *fast, *slow;
    fast = head, slow = head;
    while (fast != nullptr && fast->next != nullptr) {
      fast = fast->next->next;
      slow = slow->next;
      if (fast == slow) {
        return true;
      }
    }
    return false;
  }
};

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//! hash表 n,n
class Solution {
 public:
  bool hasCycle(ListNode *head) {
    std::unordered_map<ListNode *, bool> hashTable;
    ListNode *node = head;
    while (node != nullptr) {
      if (hashTable.find(node) != hashTable.end()) {
        return true;
      }
      hashTable[node] = true;
      node = node->next;
    }
    return false;
  }
};