首页 > 代码库 > LeetCode: Linked List Cycle II [142]
LeetCode: Linked List Cycle II [142]
【题目】
Given a linked list, return the node where the cycle begins. If there is no cycle, return null
.
Follow up:
Can you solve it without using extra space?
【题意】
给定一个单向链表,如果链表有环,则返回环开始的位置。【思路】
仍然是维护两个指针, p1, p2, p1每次走一步, p2每次走两步假设进入环之前要走X步,环长为y步,p2第一次追上p1时,p1在环上走了z步, 则有
x+y+z = 2(x+z) => y=x+z => y-z=x
y-z是第一次相遇点离环进入点的步长,这说明第一次相遇点距离环进入点与链表起始点到环入口的步长相等。
所以当第一次相遇后,p2返回链表头,然后也以一步速和p1同时向前走,则p1和p2再次相遇的点即为环入口
【代码】
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *detectCycle(ListNode *head) { if(head==NULL)return NULL; //确定第一次相遇点 ListNode* p1=head; ListNode* p2=head; while(p2){ //p1向前移动一步 p1=p1->next; //p2向前移动两步 p2=p2->next; if(p2) p2=p2->next; if(p2 && p1==p2) break; } //如果没有环 if(p2==NULL)return NULL; //如果有环 //p2指向链表头 p2=head; //p1p2都已一步速向前推进,直至相遇 while(p1!=p2){ p1=p1->next; p2=p2->next; } return p1; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。