环形链表-注意起始双指针的位置
题目描述：
个人题解：
快慢指针法，注意起始双指针的位置，一个在head位置，一个在head->next的位置，慢指针每次只移动一步，而快指针每次移动两步。初始时，慢指针在位置 head，而快指针在位置 head->next。这样一来，如果在移动的过程中，快指针反过来追上慢指针，就说明该链表为环形链表。否则快指针将到达链表尾部，该链表不为环形链表。
代码实现：
bool hasCycle(struct ListNode* head) {
if (head == NULL || head->next == NULL) {
return false;
}
struct ListNode* slow = head;
struct ListNode* fast = head->next;
while (slow != fast) {
if (fast == NULL || fast->next == NULL) {
return false;
}
slow = slow->next;
fast = fast->next->next;
}
return true;
}
复杂度分析：
时间复杂度：O(N)，其中 N 是链表中的节点数。
当链表中不存在环时，快指针将先于慢指针到达链表尾部，链表中每个节点至多被访问两次。
当链表中存在环时，每一轮移动后，快慢指针的距离将减小一。而初始距离为环的长度，因此至多移动 N 轮。
空间复杂度：O(1)。我们只使用了两个指针的额外空间。
原文地址：https://blog.csdn.net/qq_45031559/article/details/142547020
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！