Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
Analysis:
Typical two pointer questions. Give two pointers fast and slow, fast run 2 steps and slow run 1 step. If there’s a cycle, finally slow == fast. If no cycle, fast == null || fast.next == null.
Time complexity: O(n)
Space complexity: O(1)
Code is below:
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public boolean hasCycle(ListNode head) { // O(n) if (head == null || head.next == null) { return false; } ListNode slow = head; ListNode fast = head.next; // while (slow != fast) { // if (fast == null || fast.next == null) { // return false; // } // slow = slow.next; // fast = fast.next.next; // } // return true; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { return true; } } return false; } }
Followup:
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.Note: Do not modify the linked list.
Follow up:
Can you solve it without using extra space?
Analysis:
Follow the figure below:
链表头是X,环的第一个节点是Y,slow和fast第一次的交点是Z。各段的长度分别是a,b,c,如图所示。环的长度是L。slow和fast的速度分别是qs,qf。
Time complexity: O(n)Space complexity: O(1)
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode detectCycle(ListNode head) { // O(n) if (head == null || head.next == null) { return null; } 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 != slow) { return null; } fast = head; while (fast != slow) { fast = fast.next; slow = slow.next; } return fast; } }