云建站源码,重庆律师网站,云服务器建网站,网站查询域名ip解析给定一个链表的头节点 head #xff0c;返回链表开始入环的第一个节点。 如果链表无环#xff0c;则返回 null。
如果链表中有某个节点#xff0c;可以通过连续跟踪 next 指针再次到达#xff0c;则链表中存在环。 为了表示给定链表中的环#xff0c;评测系统内部使用整…给定一个链表的头节点 head 返回链表开始入环的第一个节点。 如果链表无环则返回 null。
如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。如果 pos 是 -1则在该链表中没有环。注意pos 不作为参数进行传递仅仅是为了标识链表的实际情况。
不允许修改 链表。
思路一快慢指针
c语言解法
struct ListNode *detectCycle(struct ListNode *head)
{struct ListNode *slowhead,*fasthead;while(fast!NULLfast-next!NULL){slowslow-next;fastfast-next-next;if(fastslow){struct ListNode* ptrhead;while(ptr!slow){ptrptr-next;slowslow-next;}return ptr;}}return NULL;
}
分析
本题要返回入环的第一个节点可以利用快慢指针的方法当快指针与慢指针相遇时两个指针都在环里再设置一个节点指向头节点再不断向后直到两个相等后则到了环开始的地方返回ptr即可
总结
本题考察判断环形指针的方法因为快指针的速度为慢指针的两倍所以两个指针相遇时快指针在环中比慢指针多走相同路程根据这个特点即可找到环开始的节点
