Java O(n) solution with explanation(didn't modify the linked list)


  • -2
    C

    My idea is simple, if a linked list doesn't has cycle, the pointer which points to current node will finally gets pointer.next == null. Otherwise, the begin node of the cycle should be the ListNode who has two previous pointer point to it. Which means, when we finished one traversal of the cycle and begin the second traversal, that node would be the first one occurs in HashMap twice. So I used a HashMap to store all the nodes we accessed. When we find the node which was already contained in this HashMap, that will be the result.

    public ListNode detectCycle(ListNode head) {
            if(head == null || head.next == null) return null;
            Map<ListNode,Integer> prev = new HashMap();
            ListNode pointer = head;
            while(pointer.next != null){
                if(prev.containsKey(pointer)) return pointer;
                else {
                    prev.put(pointer,1);
                    pointer = pointer.next;
                }
            }
            return null;
    }

  • 0
    P

    What is wring with this logic! What's the need to dislike it?!


  • 0
    C

    Thank you for your support Pradeep, I have no idea why some guys don't like my solution:)


  • 0
    H

    It will use extra space.


Log in to reply
 

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