CareerCup

There is well known solution for finding loops in the list.
Maintain two pointers fast and slow.
fast change as follows fast = fast.next.next
slow change as follows slow= slow.next
If they meet at some point then there is a loop.
If fast reach the end of the list then there is no loop.

An implementation of the "fast and slow pointers" solution. The fast pointer moves two steps every time and the slow pointer only moves one step. If they meet at some point then there is a loop.

struct ListNode { 
	int value; 
	ListNode *next; 
};

bool hasLoops(ListNode *myList) { 
	ListNode *fast = myList, *slow = myList;

	while (true) {
		fast = fast->next;
		if (fast != NULL) {
			/* the second move */
			fast = fast->next;
		}

		slow = slow->next;

		if (fast == NULL) {
			return false;
		}

		if (fast == slow) {
			return true;
		}
	}
}

In C++:

bool hasLoops(Node* head)
{
    if(head == NULL || head->next == NULL) return false;
    
    //at least two nodes or a one-node loop
    Node *pSlow = head->next, *pFast = pSlow->next;
    if(pFast == NULL) return false;

    //every time, move pFast two nodes and pSlow one node forward
    //if list has an end, pFast must get there first
    for(; true; pFast = pFast->next, pSlow = pSlow->next){
        if(pFast == pSlow) return true;

        pFast = pFast->next;
        if(pFast == NULL) return false;
    }

    return false;
}

Java code for the same algo - thanks to @thelineofcode

public class LoopInLinkedList {
	
	private static class Node
	{
		Node next = null, prev = null;
	}
	
	public static void main(String[] args)
	{
		Node head = new Node();
		Node currentNode = head, prevNode = head;
		
		//Adding 12 nodes to the linked list. Modify the # to add more or less nodes
		for(int i=0; i<12; i++)
		{
			currentNode.next = new Node();
			prevNode = currentNode;
			currentNode = currentNode.next;
			currentNode.prev = prevNode;
		}
		
		//Comment out the following line to avoid the loop or point to a specific node in the linked list
		currentNode.next = currentNode.prev.prev.prev.prev.prev;
		
		Node fast = head, slow = head;
		while(true)
		{
			if(fast != null)
				fast = fast.next;
			else
				break;
			 
			if(fast != null)
				fast = fast.next;
			else
				break;
			
			if(slow != null)
				slow = slow.next;
			else
				break;
			
			if(fast == slow)
				break;
		}
		
		if(fast == slow)
			System.out.println("Found a loop!");
		else
			System.out.println("Could not find a loop!");
	}
}

public class ListLoopQuestion { 

public static class ListNode { 

public int value; 

public ListNode next; 
} 

public static boolean hasLoops( ListNode myList ) { 
	if(myList == null || myList.next == null) {
		return false;
	}

ListNode slow = myList;
	ListNode fast = myList.next; // this pointer is going to travel twice as fast as the first

	// If we find a null value as a next element then we don’t have loops
while(fast != slow) {
		slow = slow.next;
		if(fast.next != null && fast.next.next != null)
			fast = fast.next.next;
		else
			return false;
	}
	
	// if the pointers meet at some point there is a loop in the list
	return true;
	
}

}

What is the algo to Find the starting point of the loop?

public static boolean hasLoops( ListNode myList ) { 
    for (ListNode hare = myList, tortoise = myList; true; ) {
        if (hare.next == null || hare.next.next == null) {
            return false;
	}
        if (hare.next == tortoise || hare.next.next == tortoise) {
            return true;
	}
        hare = hair.next.next;
        tortoise = tortoise.next;
    }
}

github.com/techpanja/interviewproblems/blob/master/src/collections/customlinkedlist/LinkedListImpl.java

#hasLoop()

careercup. com/question?id=5968086721101824

public static boolean hasLoops(listNode mylist){
listNode slow=mylist;
listNode fast =mylist;
while(fast!=null && fast.next!=null){
slow=slow.next;
fast = fast.next.next;
if(slow==fast){
break;
}
if(fast == null || fast.next ==null){
return null;
}
slow=mylist;
while(slow!=fast){
slow=slow.next;
fast=fast.next;
}
return fast;
}

Finding a loop in linked list single iteration:
we can use HashSet implementation of java. Below is code:

Public boolean hasLoop(Node linkList) {
if (linkList == null)
	return false;
Set address = new HashSet();
while(linkList.next !=  null) {
	if(address.contains(linkList.next)){
		return true;
	} else 
		address.add(linkList.next);
}
return false;
}

what if the loop is bigger? I mean if the loop is not between the adjacent nodes. I am thinking if we put the addresses of each node in an array or hashmap as we traverse the linked list...and search if the address is already in the array before putting a new one..would cover the above scenario.

Thoughts?