首页 > 代码库 > LeetCode:Linked List Cycle II
LeetCode:Linked List Cycle II
题目描述:
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?
思路:
设置一个快指针fast,一个慢指针slow。快指针一次移动两个单位,慢指针一次移动一个单位。如图,链表进入环之后是逆时针移动,假设两个指针是在红蓝交界的地方相遇。则快指针走的距离Sf=x+y+z+y=x+2y+z,慢指针走的距离Ss=x+y。又因为Sf=2Ss,则x+2y+z=2x+2y,可得x=z。则可令fast指针重新回到head,两指针依次移动一个单位直到相遇。相遇的点即为环开始的点。
代码:
ListNode * Solution::detectCycle(ListNode * head) { if(head == NULL) return NULL; if(head->next == head) return head; ListNode * fast = head; ListNode * slow = head; while(fast != NULL && fast->next != NULL) { fast = fast->next->next; slow = slow->next; if(fast == slow) break; } if(fast == NULL || fast->next == NULL) return NULL; else { fast = head; while(fast != slow) { fast = fast->next; slow = slow->next; } return fast; } }
LeetCode:Linked List Cycle II
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。