leetcode

142. 环形链表 II

力扣链接

快慢指针

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
      ListNode *slow = head, *fast = head;
      // 错误 while(fast->next && fast->next->next)
      while (fast && fast->next){
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast){
          ListNode* node1 = slow, *node2 = head;
          while (node1 != node2){
            node1 = node1->next;
            node2 = node2->next;
          }
          return node1;
        }
      }
      return nullptr;
    }
};

哈希表

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        std::unordered_set<ListNode*> uset;
        ListNode* current = head;
        while(current){
            if (uset.find(current)!=uset.end()){
                return current;
            }
            uset.insert(current);
            current = current->next;
        }
        return nullptr;
    }
};

This site is open source. Improve this page.