Solution
1.有环则说明不存在尾节点,不存在尾节点的下一个结点为NULL,一个简单的想法是遍历链表并不断存储已经遍历过的链表-最后每次遍历的时候都去check当前结点的下一个结点是不是已经遍历过的结点,java可以用hash表直接用contains函数,这里我使用的比较笨的办法,时间复杂度O(
n
2
n^2
n2),空间复杂度O(n).-容易翻车。
class Solution { //有环的时候应该就是最后一个尾结点的指向不是NULL,也就是说链表没有尾节点 public: bool hasCycle(ListNode *head) { ListNode *A[30]={}; //若测试用例长度太大就不行 int i=0; ListNode *cur=head; while(cur!=NULL and cur->next!=NULL){ for(int j=0;jnext==A[j]){ return true; } } A[i++]=cur; cur=cur->next; } return false; } };
2.经典的快慢指针
快慢指针的思想就是只要存在环,那么快指针最终肯定会与慢指针相遇一次。而如果没有环,则遍历完了两者都不会相遇。
class Solution { //有环的时候应该就是最后一个尾结点的指向不是NULL,也就是说链表没有尾节点 public: bool hasCycle(ListNode *head) { ListNode *fast=head; ListNode *slow=head; while(fast!=NULL and fast->next!=NULL){ fast=fast->next->next; //fast指针一次走两步 slow=slow->next;//slow一次走一步 if(fast==slow){ return true; } } return false; } };
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)