/* Creates a node for given data and return pointer to it. */
PNODE create_node(int x)
{
	PNODE pTemp;

	pTemp = (PNODE) malloc (sizeof(NODE));
	if (pTemp == NULL)
	{
		printf("Out of memory, could not store number!\n");
	}
	else
	{
		pTemp->x = x;
		pTemp->next = NULL;
	}

	return pTemp;
}

/* Inserts node pNew into pList, keeping list in sorted order. */
PNODE insert_node(PNODE pList, PNODE pNew)
{
	PNODE pPrev, pCur;

	/* Inserting pNew into an empty list, it just becomes list. */
	if (pList == NULL)
		return pNew;

	/* If pNew->x is less than pList->x, pNew becomes start of the list. */
	if (pNew->x < pList->x)
	{
		pNew->next = pList;
		pList = pNew;
		return pList;
	}

	/* Otherwise, find its position and put it there. */
	pPrev = pList;
	pCur = pList->next;
	while ((pCur != NULL) && (pCur->x < pNew->x))
	{
		pPrev = pCur;
		pCur = pCur->next;
	}
	pNew->next = pCur;
	pPrev->next = pNew;
	return pList;
}

/* Increase count of integer x or insert new node in sorted list. */
PNODE insert_integer(PNODE pList, int x)
{
	PNODE pPrev, pCur, pNew;

	/* Check if we are starting new list. */
	if (pList == NULL)
	{
		pNew = create_node(x);
		return pNew;
	}

	/* Otherwise, find its position and put it there. */
	pPrev = NULL;
	pCur = pList;
	while ((pCur != NULL) && (pCur->x < x))
	{
		pPrev = pCur;
		pCur = pCur->next;
	}

	if ((pCur != NULL) && (pCur->x == x))
	{
		/* Integer has occurred before, increase count. */
		pCur->count = pCur->count + 1;
	}
	else if (pPrev == NULL)
	{
		/* New integer is first in list up to this point. */
		pNew = create_node(x);
		pNew->next = pList;
		pList = pNew;
	}
	else
	{
		/* New integer goes between pPrev and pCur. */
		pNew = create_node(x);
		pNew->next = pCur;
		pPrev->next = pNew;
	}

	return pList;
}

/* Delete pNode from list starting at pHead. */
PNODE delete_node(PNODE pHead, PNODE pNode)
{
	PNODE pTemp;

	/* Check if pNode is first node. */
	if (pHead == pNode)
	{
		/* Delete first node and free memory */
		pHead = pNode->next;
		free(pNode);
		return pHead;
	}

	/* Find node previous to pNode. */
	for (pTemp = pHead; pTemp->next != pNode; pTemp = pTemp->next);

	/* Delete pNode and free memory. */
	pTemp->next = pNode->next;
	free(pNode);

	return pHead;
}

/* Iterative solution for reversing a linked list */
PNODE reverse_list(PNODE pList)
{
	PNODE pPrev, pCur, pNext;

	if (pList == NULL)
		return NULL;

	pPrev = NULL;
	pCur = pList;
	do
	{
		pNext = pCur->next;
		pCur->next = pPrev;
		pPrev = pCur;
		pCur = pNext;
	} while (pCur != NULL);

	return pPrev;
}

/* Recursive solution for reversing a linked list */
PNODE reverse_list(PNODE pList)
{
	PNODE pTemp;

	if (pList == NULL)
		return NULL;

	if (pList->next == NULL)
		return pList;

	pTemp = reverse_list(pList->next);
	pList->next->next = pList;
	pList->next = NULL;
	return  pTemp;
}