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;
}
Monday, 16 May 2011
Find the Loop in the linked list and remove the loop from it
Labels:
c,
data structure
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment