current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 0 down vote favorite

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

  1. 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?

  2. 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<E> {

    private Node<E> first;
    private Node<E> last;

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

    private static class Node<E> {
        E element;
        Node<E> next;

        Node(E element, Node<E> next) {
            this.element = element;
            this.next = next;
        }
    }


    public boolean hasLoop() {
        Node<E> fast = first;
        Node<E> slow = first;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }
   }
share|improve this question
1  
I know this is for an interview, but if I were hiring, I would want you to tell me that you would design the linked list api such that you would never end up with a loop. –  toto2 Sep 3 '13 at 18:57
    
@toto2 And how would you show that your library created good loops? With a test - one that should become a unit test, bundled with the library source. If you tried to tell me that the test was not necessary, I would know never to hire you. –  itsbruce Jan 8 at 1:38
    
@itsbruce Agreed that it makes sense as a unit test. It should probably not be a public class method however. And I still stand by my main point that the public api of that linked list class should never allow a loop to be created. –  toto2 Jan 10 at 15:45
    
possible duplicate of Linked list loop detection in Java(interview question) –  pgreen2 Jul 22 at 13:18

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
    
where would u add the static function ? Would it be in the 'DetectLoopExistance' class or in another UtilityClass ? If its added in DetectLoopExistance the it would it take List as parameter ? If it does then if i want to sort an instance, I would need to do somthing like DetectLoopExistance.mersort(instance) rather than instance.mergeSort(). If I create a utility function then it how would it do ptr.next, when next belongs to 'private nested class' ? –  JavaDeveloper Sep 4 '13 at 2:53
    
i would go for another utility class. DetectLoopExistance.mergeSort(someList) wouldn't really make sense although SortHelper.mergeSort(someList) would. For the ptr.next thing I guess I would try and find the implementation of the default sort functions and see how it is done there. –  fly.floh Sep 6 '13 at 8:32
    
Thanks but how would For the ptr.next be used ? I mean for all linkedlist interview questions we need to use ptr.next ? What would we do it then ? –  JavaDeveloper Sep 8 '13 at 5:33
up vote 2 down vote

Your loop detection will almost always take longer than the classic hare and tortoise implementation; in the case where the entire list is one loop, it will take nearly twice as long. Consider that latter case:

You will not detect the loop until the slow node has caught up with the fast node, while the classic implementation detects when fast catches and passes slow. Your implementation will only return when slow has run once through the list and returned to the first node (and fast has therefore looped twice through the list). The classic method will return once slow has reached list.size() - 2 where list.size() is even or list.size() - 1 where it is odd (this is the point at which it will be lapped). In a list of 1 or 2 nodes, slow never moves at all.

Adapting your version minimally to make it into the classic implementation gives this:

public boolean hasLoop() {
  Node<E> fast = first;
  Node<E> slow = first;

  while (fast != null && fast.next != null) {
    if (slow == fast.next || slow == fast.next.next) {
      return true;
    } else {
      fast = fast.next.next;
      slow = slow.next;
    }
  }
  return false;
}

This can be optimised to remove the duplicated iterations of fast.next but I left it like this for greater clarity.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.