#include <stdio.h>

typedef enum { FALSE, TRUE } bool;

/* Declaration of Node type */
typedef struct node_s {
	int data;
	struct node_s *next;
} node_t;

/*
** Detection: Have two pointers into the list (ptr and depar). Advance depar twice as
** fast as ptr; if they ever point to the same place then the list
** has a loop in it.
**
** Removal: Leave one pointer(depar) in place where the two pointers in the previous
** step met, and another pointer(ptr) pointing to the head, advance these two by 1 step
** each till the next node to each is the same. The node pointer with depar will be the
** last node, so set it's next to NULL.
*/
bool findAndRemoveLoop (node_t *head)
{
	node_t *ptr = head;
	node_t *depar = head;
	bool ret = FALSE;		// the return value
	
	// this loop detects the loop
	while (depar) {
		ptr = ptr->next;
		if ((depar = depar->next) && (depar = depar->next) && depar == ptr) {
			ret = TRUE;
			break;
		}
	}
	
	// this part removes the loop
	if (ret == TRUE) {
		ptr = head;
		while(ptr->next != depar->next) {
			ptr = ptr->next;
			depar = depar->next;
		}
		if(ptr == depar) {				// note that this means it's a circlic list
			while(depar->next != ptr) {	// iterate through the last (prev) node
				depar = depar->next;
			}
		}
		depar->next = NULL;				// this points to the last node
	}
	
	return ret;
}


////////////////////// TEST CODE ///////////////////////


node_t nodearr[10];

void initNodes()
{
	int i;
	
	// initialize the nodes
	for(i = 0; i < 10; i++) {
		nodearr[i].data = i;
		nodearr[i].next = NULL;
	}
}

void printList(node_t *head)
{
	int limit = 20;
	while(head && (--limit)) {
		printf("%d->",head->data);
		head = head->next;
	}
	printf("\n");
}

int main()
{
	int i;
	node_t * head;
	
	initNodes();
	
	// establish the linked list
	for(i = 0; i < 9; i++) {
		nodearr[i].next = &nodearr[i+1];
	}
	head = &nodearr[0];
	
	// Scenario 1: No loop
	printf("Scenario 1: No loop\n");
	printList(head);
	printf("Scenario 1: After removal\n");
	findAndRemoveLoop(head);
	printList(head);
	
	// Scenario 2: Loop from node 5	
	// let's have the list loop from node 5
	nodearr[9].next = &nodearr[4];
	printf("Scenario 2: Loop from node 5\n");
	printList(head);
	findAndRemoveLoop(head);
	printf("Scenario 2: After removal\n");
	printList(head);
	
	// Scenario 3: Circlic list
	nodearr[9].next = &nodearr[0];
	printf("Scenario 3: Circlic list\n");
	printList(head);
	findAndRemoveLoop(head);
	printf("Scenario 3: After Removal\n");
	printList(head);	
	
	return 0;
}