CareerCup

If the linked list does not contain a cycle, then this partial function is injective (one-to-one), meaning that no two nodes map to the same successor. Injective functions can indeed be inverted, which is why you can reverse a regular linked list. However, if the list contains a cycle, then there are two nodes with the same successor, so the function is not injective and thus does not have an inverse. So no, you cannot reverse the linked list and expect to get another linked list, if the list has a cycle.

However, if you treat the linked list as a more general graph in which each node can have any number of incoming or outgoing edges, then the inverse does exist. It's just not a linked list anymore.

1. use three node pointers to keep the preNode, curNode, nextNode, and change their next pointers.
initially: preNode = NULL; curNode = head; nextNode = head->next;
then update: curNode->next = preNode; preNode = curNode; curNode = nextNode, nextNode = nextNode->next.
of course, be careful to boundary cases such no or only one node in the list

2 and 3, use two nodes with different travel speed, the fast one will meet or over with the slower one when their is loop.

To find a Loop in link list is a two runners Problem.

Take two Pointers Like P and Q.

Change both with different speed Like p=p->next; q=q->next->next;
If at any Place they will be equal and It means Loop is there

1. Using recursion for reversing a linked list avoids using extra variable.Agreed, call stack will be used but manual manipulations can be avoided.So I feel.

Code:

NODE *head; //pointer to the first node of list

Recur_rev(NODE *p)
{
if(p->next != NULL)
{
Recur_rev(p->next);
p->next->next = p;
}
else
head = p;

}

2. Agreed with Surender and proboy. To find the the starting node from where the loop starts, just find the number steps taken by any of the nodes(P or Q) on their meeting.
Then, start from beginning of list again.Increment first pointer in unit steps and the second with the number calculated above
When both the pointers point to the same node, there you have your starting node.

bool isLoopExist(struct node * root )
{
struct node *p,*q;
if( root == NULL )
return false;
p = root;
q = p->next;
while( q ! = NULL )
{
if( p == q )
return true;
p = p->next;
q = (q->next == NULL ) ? q->next : g->next->next ;
}
return false;
}

But the last part ..remains how do we know where the loop exists??

1.Take two pointer
2.keep moving first node by one node and second by two node
3.In each step check whether both pointers are same or not after crossing first node.
4.If both pointers are pointing to same node that means loop exists return current node.
5.If not and both pointers reached to null that means... no loop exists...!!

This method is also dependent on Floyd’s Cycle detection algorithm.
1) Detect Loop using Floyd’s Cycle detection algo and get the pointer to a loop node.
2) Count the number of nodes in loop. Let the count be k.
3) Fix one pointer to the head and another to kth node from head.
4) Move both pointers at the same pace, they will meet at loop starting node.
5) Get pointer to the last node of loop and make next of it as NULL.

start with 2 pointer let t1 nd t2.
move t1 pointer by 1 nd t2 pointer by 2.
if at any time t1==t2 then we have a loop in the list.

for start point take third pointer t3 nd start t3 from start.
t1 nd t2 will be moving in the loop only.
dont change t1 nd increase t2.
move t2 one by one nd chk if t3==t2.
if t2==t1 then increment t3. nd keep chking like this if any time t2==t3 then t3 is the starting of the loop.