首页 > 代码库 > [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?
Hide Tags
Linked List Two Pointers 开始犯二了一点，使用了node 的val 作为判断，其实是根据内存判断。找出链表环的起始位置，这个画一下慢慢找下规律便可以：
思路：
- 使用快慢指针，慢指针每次前进一步，快指针每次两步
- 如果快慢指针相遇了，那么将快指针从标记带链表头，改为每次前进一步
- 当快慢指针再次相遇便是环起始位置。
这样的实现，时间很快O(n)，而且空间O(1)
#include <iostream>using namespace std;/** * 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 * fast=head,*slow=head; while(1){ if(fast->next!=NULL) fast=fast->next; else return NULL; if(fast->next!=NULL) fast=fast->next; else return NULL; slow=slow->next; if(fast==slow) break; } fast=head; while(1){ if(fast==slow) return slow; fast=fast->next; slow=slow->next; } return NULL; }};int main(){ ListNode node1(1),node2(2),node3(3),node4(4),node5(5); node1.next=&node2; node2.next=&node3; node3.next=&node4; node4.next=&node5; node5.next=&node1; Solution sol; ListNode *ret = sol.detectCycle(&node1); if(ret==NULL) cout<<"NULL"<<endl; else cout<<ret->val<<endl; return 0;}
[LeetCode] Linked List Cycle II 链表环起始位置
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。