Given a linked list, determine if it has a cycle in it.
To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.
Example 1:
Input: head = [3,2,0,-4], pos = 1 Output: true Explanation: There is a cycle in the linked list, where tail connects to the second node.Example 2:
Input: head = [1,2], pos = 0 Output: true Explanation: There is a cycle in the linked list, where tail connects to the first node.Example 3:
Input: head = [1], pos = -1 Output: false Explanation: There is no cycle in the linked list.
Follow up:
Can you solve it using O(1) (i.e. constant) memory?
------------------------------------------------------------------------------------------------------------------------------------------------------
用中文来说,这个题就是判断一个链表是否存在环。可以用双指针来解决。即可以建立一个慢指针和快指针,最后两个指针相遇,就可以判断相等。
C++代码:
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ bool hasCycle(struct ListNode *head) { struct ListNode *slow,*fast; slow = head; fast = head; while(fast && fast->next){ //如果fast=NULL或fast->next=NULL就说明了链表一定没有环,只是一个单链表而已。 slow = slow->next; fast = fast->next->next; if(slow == fast) return true; } return false; }
转载于:https://www.cnblogs.com/Weixu-Liu/p/10704019.html