Monday, 16 May 2011

Find the Loop in the linked list and remove the loop from it



int detectLoop(NODE* headNode)
{
NODE* oneStepPtr = headNode;
NODE* twoStepPtr = headNode;
int isLoop = 0;

while(twoStepPtr != NULL
&& twoStepPtr->next != NULL
)
{
oneStepPtr = oneStepPtr->next;
twoStepPtr = twoStepPtr->next->next;

if (twoStepPtr == oneStepPtr)
{
isLoop = 1;
break;
}
}
return isLoop;
}

/* Call only when loop exists */
void removeLoop(NODE* headNode)
{
/* find Loop Node */
NODE* oneStepPtr = headNode;
NODE* twoStepPtr = headNode;
NODE* loopNode = headNode;

while(twoStepPtr != NULL
&& twoStepPtr->next != NULL
)
{
oneStepPtr = oneStepPtr->next;
twoStepPtr = twoStepPtr->next->next;

if (twoStepPtr == oneStepPtr)
{
loopNode = oneStepPtr;
break;
}
}


/* Find loopLength */
NODE* currentNode = loopNode;
int loopLength = 0;
while (currentNode != loopNode
|| loopLength == 0)
{
loopLength++;
currentNode = currentNode->next;
}


/* Offset headNode by loopLength */
currentNode = headNode;
NODE* offSetNode = NULL;
NODE* tailNode = NULL;
int offSetLength = 0;

while(offSetLength < loopLength) { tailNode = currentNode; currentNode = currentNode->next;
offSetLength++;
}
offSetNode = currentNode;


/* find tailNode, when currentNode and offSetNode meets, but one */
currentNode = headNode;
while(offSetNode != currentNode)
{
tailNode = offSetNode;
offSetNode = offSetNode->next;
currentNode = currentNode->next;
}

tailNode->next = NULL;
}

No comments:

Post a Comment