首页 > 代码库 > Linked List Cycle 判断一个链表是否存在回路(循环)
Linked List Cycle 判断一个链表是否存在回路(循环)
Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
注意，链表循环并不是尾指针和头指针相同，可能是在中间某一段形成一个环路，所以不能只判断元素和第一个元素是否存在重合
先设置两个指针p_fast和p_slow。从头开始遍历链表，p_fast每次走两个节点，而p_slow每次走一个节点，若存在循环，这两个指针必定重合：
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 class Solution {10 public:11 bool hasCycle(ListNode *head) {12 if(head == NULL) return false;13 14 ListNode *p_fast = head;15 ListNode *p_slow = head;16 17 do{18 p_slow = p_slow->next;19 if(p_fast != NULL)20 p_fast = p_fast->next;21 if(p_fast != NULL)22 p_fast = p_fast->next;23 else24 return false;25 }while(p_fast != p_slow);26 27 return true;28 29 }30 };
Linked List Cycle 判断一个链表是否存在回路(循环)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。