【力扣 简单 C】141. 环形链表

目录

题目

解法一：记录遍历过的结点（哈希集合）

解法二：快慢指针

---

题目

解法一：记录遍历过的结点（哈希集合）

typedef struct hashSetListNode
{void* val;struct hashSetListNode* next;
} hashSetListNodeType;typedef struct hashSet
{hashSetListNodeType** bucket;uint32_t size;
} hashSetType;hashSetType* hashSetInit(uint32_t size)
{hashSetType* hashSet = malloc(sizeof(*hashSet));hashSet->bucket = calloc(size, sizeof(*hashSet->bucket));hashSet->size = size;return hashSet;
}// FNV-1a
uint32_t hash(const uint8_t* data, uint32_t len)
{uint32_t hash = 0x811c9dc5;for (int i = 0; i < len; i++){hash ^= data[i];hash *= 0x01000193;}return hash;
}void hashSetInsert(hashSetType* hashSet, void* val)
{uint32_t index = hash((uint8_t*)&val, sizeof(val)) % hashSet->size;hashSetListNodeType* newNode = malloc(sizeof(*newNode));newNode->val = val;newNode->next = hashSet->bucket[index];hashSet->bucket[index] = newNode;
}bool hashSetFind(hashSetType* hashSet, void* val)
{uint32_t index = hash((uint8_t*)&val, sizeof(val)) % hashSet->size;hashSetListNodeType* curNode = hashSet->bucket[index];while (curNode){if (curNode->val == val)return true;curNode = curNode->next;}return false;
}void hashSetFree(hashSetType* hashSet)
{for (int i = 0; i < hashSet->size; i++){hashSetListNodeType* freeNode = hashSet->bucket[i];while (freeNode){hashSetListNodeType* nextNode = freeNode->next;free(freeNode);freeNode = nextNode;}}free(hashSet->bucket);free(hashSet);
}bool check(struct ListNode* head)
{hashSetType* hashSet = hashSetInit(512);struct ListNode* curNode = head;bool is = false;while (curNode){if (hashSetFind(hashSet, curNode)){is = true;break;}hashSetInsert(hashSet, curNode);curNode = curNode->next;}hashSetFree(hashSet);return is;
}bool hasCycle(struct ListNode* head)
{return check(head);
}

解法二：快慢指针

bool check(struct ListNode* head)
{struct ListNode* fast = head;struct ListNode* slow = head;while (fast && fast->next){fast = fast->next->next;slow = slow->next;if (fast == slow)return true;}return false;
}bool hasCycle(struct ListNode* head)
{return check(head);
}