Share my accepted Java solution!


  • 1
    I
    public class Solution {
        public ListNode detectCycle(ListNode head) {
            ListNode result = null;
            HashSet<ListNode> set = new HashSet<ListNode>();
            while(head != null) {
                if (set.contains(head)) {
                    result = head;
                    break;
                }
                set.add(head);
                head = head.next;
            }
            return result;
        }
    }
    

    Another solution using Floyd's cycle-finding algorithm.

    public class Solution {
        public ListNode detectCycle(ListNode head) {
            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 == null || fast.next == null) return null;
            slow = head;
            while(slow != fast) {
                slow = slow.next;
                fast = fast.next;
            }
            return fast;
        }
    }

  • 0
    H

    have to do it without using memory, with extra memory is trivial.


  • 0
    W

    I just try to run your second solution and it gives TLE....Not sure why....


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.