struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
bool hasCycle(ListNode *head) {
if(head == NULL) return false;
ListNode* walker = head;
ListNode* runner = head;
while(runner->next != NULL && walker->next != NULL){
walker = walker->next;
runner = runner->next->next;
if(walker == runner) return true;
}
return false;
}
};
我正在练习一个看起来很简单的面试代码。我必须返回一个布尔值来确定单链表是否有循环。我制作了两个指针步行器(每次迭代移动 1 步)和跑步器(每次迭代移动 2 步)。
但是这段代码给了我一个错误:
Line 15: member access within null pointer of type 'struct ListNode'
导致该错误的原因是什么?
您只需确保
runner->next
不为空,但在赋值之后
runner = runner->next->next;
runner
可以变为空。
这应该可以解决问题:
bool hasCycle(ListNode *head) {
if(head == NULL || head->next == NULL) { return false; }
struct ListNode * walker = new ListNode(1);
struct ListNode * runner = new ListNode(2);
walker = head;
runner = walker->next;
while(walker != fast){
if(runner == NULL || runner->next == NULL) { return false; }
walker = walker->next;
runner = runner->next->next;
}
return true;
}
//- 如果从圆形路径形成一个循环,那么它们有 100% 的机会在某个点相遇,所以这里我们采用一个移动一步的步行者和一个移动两步的跑步者。
bool hasCycle(ListNode *head){
if(head == NULL || head->next == NULL)
return false;
struct ListNode *temp = head;
struct ListNode *walker;
struct ListNode *runner;
walker = runner= head;
while(temp ){
walker = walker->next;
runner = runner->next->next;
if(runner == walker) // as soon both get at same address we got return as
true value.
{ return True; }
temp = temp->next;
}
return false;
}
下面的代码应该可以正常工作。
这是经典的野兔-乌龟定理,兔子走2步(距离单位),而乌龟走1。
我认为您没有检查导致此错误的
runner->next->next
的无效性
bool hasCycle(ListNode *head)
{
if(head == NULL || head->next == NULL)
{
return false;
}
ListNode* tortoise=new ListNode();
ListNode* hare = new ListNode();
tortoise=head;
hare=tortoise->next;
while(tortoise != hare)
{
if(hare == NULL || hare->next == NULL)
{
return false;
}
tortoise=tortoise->next;
hare=hare->next->next;
}
return true;
}
排序答案和解释在这里
它返回错误,因为
可以为 NULL 并且您在调节时检查 runner->next!=NULL ,以便您 必须在代码中做一些更改才能得到答案 同时条件检查runner=runner->next->next
并获得正确的结果 回答。runner->next->next!=NULL