Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
Can you solve it without using extra space?
使用快慢指针,快指针走两部,慢指针走一步,如果两者相同则有环。
public class Solution { //Time: O(n) Space: O(1) public boolean hasCycle(ListNode head) { if (head == null || head.next == null) { return false; } ListNode fast = head; ListNode slow = head; while (fast.next != null && fast.next.next != null) { fast = fast.next.next; slow = slow.next; if (slow == fast) { return true; } } return false; } }
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?
当判断有环后,让head和slow每次都一步,相遇即为环起点。
Can you solve it without using extra space?
当判断有环后,让head和slow每次都一步,相遇即为环起点。
public class Solution { //Time: O(n) Space: O(1) public ListNode detectCycle(ListNode head) { if (head == null || head.next == null) { return null; } ListNode fast = head; ListNode slow = head; while (fast.next != null && fast.next.next != null) { fast = fast.next.next; slow = slow.next; if (slow == fast) { break; } } if (fast.next == null || fast.next.next == null) { return null; } while (head != slow) { slow = slow.next; head = head.next; } return slow; } }
No comments:
Post a Comment