CareerCup

umairsaeed.com/2011/06/23/finding-the-start-of-a-loop-in-a-circular-linked-list/

Its simple problem if you can you know how to find whether a list have loop or not.
Algorithm :- Take two pointers p1 and p2. Start both from head. Loop until p1 and p2 meet again. But p1 will incre one step i.e. p1 = p1-> next and p2 will two steps i.e. p2= p2->next->next.Once they meet. Do following step.
Now make p1=head and start increment one step by one for both p1 and p2. When they meet again will be the starting point of the cycle.

public static LinkedList.Node findCircular(LinkedList.Node head)
    {
        HashSet<LinkedList.Node> hs= new HashSet<>();
        LinkedList.Node tempNode= head, prevNode= null;
        while(!hs.contains(tempNode))
        {
            hs.add(tempNode);
            prevNode= tempNode;
            tempNode= tempNode.next;
        }
        
        return prevNode;
    }

My code, check Linkedlist has cycle and return entry node of cycle:
public static LinkedListNode find_cycle_entry(LinkedListNode head){
if(head==null){
System.out.println("err, no cycle!");
return null;
}
LinkedListNode slow=head.next;
if(slow==null){
System.out.println("err, no cycle!");
return null;
}
LinkedListNode fast=head.next.next;
if(fast==null){
System.out.println("err, no cycle!");
return null;
}

while(fast!=null){
if(slow==fast){
break;
}
slow=slow.next;
fast=fast.next;
if(fast==null){
System.out.println("err, no cycle!");
return null;
}
fast=fast.next;
}

if(fast==null){
System.out.println("err, no cycle!");
return null;
}
slow=head;
while(slow!=fast){
slow=slow.next;
fast=fast.next;
}
return slow;
}

void FindHead(struct Node **start)
{
Node *elem = *start;
while(elem->data < elem->next->data)
{
elem = elem->next;
}
*start = elem->next;
}

How you are returning the Node from where cycle is starting. Can you write down steps in seperate lines?

Given two iters A,B, such that A is always ahead of B. If both A,B are in a circle, then going forward from A, it should be possible to reach B. Since we don't know ahead of time how many steps it will take to reach B, let's accelerate after each iteration, i.e. step++; otherwise, if step is constant, it may take many more iterations before A overtakes B...

static Node findStart(final Node[] list) {
        int step = 1;

        if (list.length <= 2) {
            return list[0];
        }

        Node headconstant = list[0];
        Node headaccel = list[2];
        boolean isLoop = false;

        while ((headaccel != null) && !isLoop) {
            for (int i = 1; i <= step; i++) {
                headaccel = headaccel.next;

                if (headaccel==headconstant) {
                    isLoop = true;

                    break;
                } else if (headaccel == null) {
                    break;
                }
            }


            headconstant = headconstant.next;
            step++;
        }

        return headaccel;
    }

One problem with the above code, though it finds a loop, it doesn't always specify where the cycle starts. In this case, you'd need additional info. Add a visitors integer K such that, if headaccel visits a node N, it sets K to 1. headaccel is only needed with a step of 1 . If headaccel visits N again, increment K to 2. If K=2, then you've detected a loop, and the start of the cycle.

Can we just traverse the list from head and each time check if the node is visited? We can have something like this in the Node class

public void setVisited() {
	visited = true;
}
public boolean getVisited() {
	return visited;
}

then we can have a method that traverse the list that returns the first node that's visited twice

public Node traverse(LinkedList<Integer> list) {
	for (Iterator<Integer> it = list.iterator(); list.hasNext();) {
		if (it.next().getVisited()) {
			return it.next();
		} else {
			it.next().setVisited();
		}
	}
	return null;
}

Used Floyd Cycle Detection Algorithm/ Tortoise and Hare algorithm

No need for slow/fast pointers. Problem definition is using characters, so:

Node* cycle_start_node(Node* n) {
  bool seen[256];
  memset(seen, false, 256*sizeof(bool));
  while (n != NULL) {
    if (seen[n->val]) return n;
    seen[n->val] = true;
    n = n->next;
  }
  return NULL;
}

take two pointers one is incrment by one and another by two and check cond whether next not equal null or the adrres of both pointers are same

As soon as you find a loop open that loop..
It will look like this..
          |-d-3-4-5-5
A-b-c-|
          |-3-4-6-8 now intersection point C can be fond quite easily.