/* 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;
}

/* 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;
}