leetcode题解-141-环形链表

发表于

题目

以下2种题解，时间均是\(O(1)\)

哈希表

额外空间: \(O(n)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) 
    {
        auto p = head;
        set<ListNode*> hash;

        while (p)
        {
            if (!hash.count(p))
            {
                hash.insert(p);
            }
            else
            {
                return true;
            }
            p = p->next;
        }   
        
        return false;
    }
};

双指针法

额外空间：\(O(1)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) 
    {
        if (!head || !head->next)   return false;
        ListNode* slowP = head;
        ListNode* fastP = head->next;

        while (slowP != fastP)
        {
            // CUZ fastP 快些，所以fastP/ fastP->next为null之后，就说明 无环了
            if (!fastP || !fastP->next) return false;
            
            slowP = slowP->next;
            fastP = fastP->next->next;        
        }

        return true;
    }
};

总结

  • 双指针法

    • 需要注意，初始化 fastP, slowP快慢指针的时候的判别条件。

      1
      2
      3
      if (!head || !head->next)   return false;
      ListNode* slowP = head;
      ListNode* fastP = head->next;

    • 判断是否有环 <=> 判断是否指针指向nullptr处. 判断指针是否指向nullptr处的常数项系数更小。

      注意此时的循环/条件语句的判别条件。

      1
      2
      3
      4
      5
      while (slowP != fastP)
      {
          // CUZ fastP 快些，所以fastP/ fastP->next为null之后，就说明 无环了
          if (!fastP || !fastP->next) return false;
      }