Detect if linked list contains a loop The following is a code to detect a loop in a linked list. This question is prepared strictly for interview purposes. This code has been modeled as per Linkedlist.java


How should I decide if a function like hasLoop() should be included as an instance method or should be a static method similar to sort in Collections.java?
Ideally I would inherit Linkedlist and add an extra function mergeSort to the subclass, but the interviewer would not like it, thus I should keep my solution without inheriting linkedlist for interview sake.  Do you agree?




    public class DetectLoopExistance&lt;E&gt; {

    private Node&lt;E&gt; first;
    private Node&lt;E&gt; last;

    public void add(E element) {
        final Node&lt;E&gt; l = last;
        final Node&lt;E&gt; newNode = new Node&lt;E&gt;(element, null);
        last = newNode;
        if (first == null) {
            first = newNode;
        } else {
            l.next = newNode;
        }
    }

    private static class Node&lt;E&gt; {
        E element;
        Node&lt;E&gt; next;

        Node(E element, Node&lt;E&gt; next) {
            this.element = element;
            this.next = next;
        }
    }


    public boolean hasLoop() {
        Node&lt;E&gt; fast = first;
        Node&lt;E&gt; slow = first;

        while (fast != null &amp;&amp; fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }
   }
To answer your first question, I would create the method as a static method, because similar to sorting, detecting loops is basic functionality, that is applicable to Lists in general, not only a specific List object.

I would not recommend inheriting from the original List implementation in order to create the merge sort functionality. If you do so you will end up with List objects that can be sorted using merge sort and List objects, that cannot. But there is not really a difference between the two in structure, the only difference is that one is you inherited version and one is the LinkedList implementation. This complicates things unnecessarily. Again I would create a static method to merge sort any List, which would add the ability to merge sort any LinkedList, any ArrayList and any other custom List implementation, that implements the Java List interface.