首页 > 代码库 > LeetCode: Linked List Cycle 解题报告
LeetCode: 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?
SOLUTION 1:
经典快慢指针问题。如果存在环，fast, slow必然会相遇。就像2个速度不一样的人在环形跑道赛跑，总有一个时间他们会相遇。
如果fast到达了null，就是没有环，可以返回false.
1 package Algorithms.list; 2 3 import Algorithms.algorithm.others.ListNode; 4 5 /** 6 * Definition for singly-linked list. 7 * class ListNode { 8 * int val; 9 * ListNode next;10 * ListNode(int x) {11 * val = x;12 * next = null;13 * }14 * }15 */16 public class HasCycle {17 public boolean hasCycle(ListNode head) {18 if (head == null) {19 return false;20 }21 22 ListNode slow = head;23 ListNode fast = head;24 25 while (fast != null && fast.next != null) {26 slow = slow.next;27 fast = fast.next.next;28 if (slow == fast) {29 return true;30 }31 }32 33 return false;34 }35 }
LeetCode: Linked List Cycle 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。