环形链表||
题目描述:给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
题解思路:采用双指针法,设置一个快指针,一个慢指针,它们采取的步长不一样,如果相遇,就代表链表一定存在环(与环形链表|一致),然后在前边的循环里利用慢指针寻找入环的第一个节点,采用标记法,访问过就标记其val值为9999999,第二次访问到val值为9999999的节点,就是我们要找的节点。
注意点:
- 小心空指针,使用
fast->next->next
要先判断fast->next
是否为空 - 由于不能修改节点信息,所以标记val值=9999999,这个值尽量取得大一点,不然不会通过一些测试实例。
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode *fast,*slow,*res;
fast=slow=head;
int flag,flag1;
flag=flag1=0;
while(fast&&fast->next&&slow)
{
if(slow->val==99999999&&!flag1)
{
flag1=1;
res=slow;
}
slow->val=99999999;
fast=fast->next->next;
slow=slow->next;
if(fast==slow)
{
flag=1;
}
if(flag1&&flag)
{
break;
}
}
if(!flag)
{
res=NULL;
}
return res;
}
借鉴其他的方法:
可证:自他们相遇后,指针1从起点每次走一步,指针2从相遇点每次走一步,指针1和指针2相遇处就是环的起点。证明如下:
如下图,设Y点为环起点,Z点为快慢指针相遇点,abc为这几个关键节点间的路程(可能包括很多节点)。
因为,相遇时快指针走过的路程肯定为慢指针走过的路程的2倍。得:
(a+b)2 = a+b+(b+c)n //n>=1,n为快指针在相遇前绕环的圈数
解方程得 a = (b+c)(n-1)+c
所以:
当n=1时,a=c
当n>1时,a=c+(n-1)圈
得证。
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode *fast,*slow,*res;
fast=slow=head;
int flag=0;
while(fast&&fast->next)
{
fast=fast->next->next;
slow=slow->next;
if(fast==slow)
{
slow=head;
while(slow!=fast)
{
fast=fast->next;
slow=slow->next;
}
res=slow;
flag=1;
break;
}
}
if(!flag)
{
res=NULL;
}
return res;
}
- 这样的话,时间会比第一种方法慢一些,因为多了一个while循环(双层)。
转载:https://blog.csdn.net/dreamLC1998/article/details/102055653
查看评论