一、要求
给定一个链表的头节点 head
,返回链表开始入环的第一个节点。 如果链表无环,则返回 null
。
如果链表中有某个节点,可以通过连续跟踪 next
指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos
来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos
是 -1
,则在该链表中没有环。注意:pos
不作为参数进行传递,仅仅是为了标识链表的实际情况。
不允许修改 链表。
二、思路
基本思路和上一个环形链表(如果有疑问可以移步上一篇博客查看)大部相同,但存在一个关键问题上的不同点。
使用快慢指针的方式来解决环形链表问题。
首先定义两个指向head的struct ListNode*类型的指针变量用来记录开始位置;
接下来判断链表是否为空链表以及链表的首项指向的地址是否为空;
确保上述条件后开始让phead1和phead2分别向前走一步和两步;
再他们向后走的过程中一旦遇到指向NULL的问题说明该链表不是环形链表;
不为NULL就继续向后走;
此时按照上述判断已经确定该链表为环形链表;
对链表的地址进行判断,当两链表指向的地址相同时说明该链表为环形链表。
关键结论:
使phead2和head同时向后一步一步的走,最终他们会在环形链表的入口处相遇!
我们在知道了这个结论以后开始对这个结论进行论证;
// // 我们假设环状链表环的起点到头部的距离为L
// // 环的长度为C
// // phead1和phead2相交的位置到环状链表环的起点的位置为X
// // 此时可以得到L = N*C-X(N为phead2多走的圈数)
// // L = (N-1) * C + C - X
// // 也就是说phead2是从x开始走的,他们两个走的距离刚好越过了X即L = N * C 两者的相遇点就是环形链表的起点
三、画图理解
ps:环形链表的论证已经在上一篇博客中详细解释,在这里不再进行过多赘述,谢谢理解。
四、代码实现
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode * phead1 = head;
struct ListNode * phead2 = head;
while(phead2&&phead2->next)
{
phead1 = phead1->next;
phead2 = phead2->next->next;
if(phead1 == phead2)
{
while(head!=phead2)
{
head= head->next;
phead2=phead2->next;
}
return head;
}
}
return NULL;
}
五、小思考
如果走的距离不是1和2,他们是否还能相遇?
后面为什么直接使用head而不是创建一个临时指针用于替代它呢?
请将答案放在评论区吧!