CareerCup

Use the Floyd's cycle-finding algorithm (tortoise and the hare).

def print_loop(head, next_ptr):
    ptr_1x = head
    ptr_2x = head

    # first iteration until ptr_2x catches up with ptr_1x
    while(True):
        if (ptr_2x != None) and (next_ptr[ptr_2x] != None) and \
           (next_ptr[next_ptr[ptr_2x]] != None):
            ptr_2x = next_ptr[next_ptr[ptr_2x]]
        else:
            return False

        ptr_1x = next_ptr[ptr_1x]

        if ptr_1x == ptr_2x:
            break

    # second iteration - reset ptr_2x and go at 1x and
    # continue ptr_1x from last location in first iteration
    # to find start of loop
    ptr_2x = head
    while(ptr_2x != ptr_1x):
        ptr_2x = next_ptr[ptr_2x]
        ptr_1x = next_ptr[ptr_1x]
    start = ptr_1x

    # print loop
    print start
    ptr_1x = next_ptr[ptr_1x]
    while(ptr_1x != start):
        print ptr_1x
        ptr_1x = next_ptr[ptr_1x]



## MAIN ##

next_ptr = {
    1 : 2,
    2 : 3,
    3 : 4,
    4 : 5,
    5 : 6,
    6 : 7,
    7 : 8,
    8 : 9,
    9 : 5
    }

print_loop(1, next_ptr)

You can use the following approach.
a.Take one pointer increment it by 2
b.Take another pointer increment it by 1.
c.If at any time first that is fast pointer reaches null then return false as loop does not exist.
d.If at any time second one that is the slow becomes equal to the first one then break.
e.Take the slow pointer to the start and then increment both by one till they become equal .That becomes the starting point of a loop in the linked list.

Solution in Java

import java.util.HashSet;


public class DetectLoops {

	public static void main(String[] arg){
		//We build a linked list from an array of Integer
		Integer[] input = {0,1,2,3,4,5,6};
				
		LinkedList<Integer> myList = new LinkedList<Integer>();
		
		Node<Integer> current = myList.head = new Node<Integer>();
		myList.head.value = input[0];
		
		Node<Integer> savedForLoop = null;
		
		for(int i=1; i<input.length; i++){
			current.next = new Node<Integer>();
			current.next.value = input[i];
			if(i == 3)
				savedForLoop = current; 
			current = current.next;
		}
		
		//Create the loop (6 -> 2)
		current.next = savedForLoop;
		
		System.out.println(myList);
	}
	
}


class LinkedList<T>{
	protected Node<T> head = null;
	
	public String toString(){
		HashSet<T> loop = hasLoop();
		if(loop.size() > 0)
			return "The linked list has a loop : " + loop;
		Node<T> current = this.head;
		StringBuilder buffer = new StringBuilder(current.value.toString());
		while(current.next != null){
			current = current.next;
			buffer.append("->" + current.value);
		}
		return buffer.toString();
	}
	
	public HashSet<T> hasLoop(){
		HashSet<T> loopValues = new HashSet<T>();
		if(head == null || head.next == null)
			return loopValues; //There are no loops!
		//We declare two runners. One advances by one value at a time, the other one advances by two
		Node<T> slow = head.next;
		Node<T> fast = head.next.next;
		Node<T> loopDetectedHere = null;
		while(fast != null && fast.next != null){
			if(fast.equals(slow)){
				//There is a loop
				loopDetectedHere = slow;
				break;
			}
			fast = fast.next.next;
			slow = slow.next;
		}
		
		if(loopDetectedHere != null){ //A loop was deteced
			Node<T> current = loopDetectedHere.next;
			while(!current.equals(loopDetectedHere)){
				loopValues.add(current.value);
				current = current.next;
			}
		}
		
		return loopValues; //There are no loops. the fast runner reached the end of the linked list
	}
}


class Node<T>{
	protected T value = null;
	protected Node<T> next = null;
	
	public boolean equalsTo(Node<T> node){
		return (node.value != null && this.value != null && node.value.equals(this.value)) || (node.value == null && this.value == null);
	}
	
	public String toString(){
		return value.toString();
	}
}

Simple.
First find whether there is loop or not (p= head->next, q=head->next->next).
If there is a loop, you will find a node where values of p and q will be same. Now print all
p->next till p->next ==p.

p=q=start;
while(q->next!=NULL&&q->next->next!=NULL)
{
      p=p->next;
      q=q->next->next;
       if(p==q)
       break;
}
if(p!=q)
return NULL;
p=start;
while(p!=q)
{
      p=p->next;
      q=q->next;
}
q=q->next;
printf("%d\n",p->num);
while(p!=q)
{
     printf("%d\n",q->num);
     q=q->next;
}

public boolean cycle(){
		Node slow = head;
		Node fast = head;
		if(head == null)
			return false;
		boolean flag =false;
		while((fast != null)){
			if(fast.next == null)
				return false;
			fast = fast.next.next;
			slow =slow.next;
			if((fast == slow) || (slow.next == fast)){
				if(slow.next == fast)
					slow = slow.next;
				flag = true;
				break;
			}
		}
		if(flag == true){
			Node n = slow;
			System.out.println("Cycle:");
			do{
				System.out.println(n.data);
				n = n.next;
			}while(n != slow);
			return true;
		}
		else
		 return false;
	}