Write a C program to remove duplicates from a sorted linked list.

void RemoveDuplicatesFromSortedList(NODE *pHead)
{
if (NULL == pHead)
return;

NODE *pCurrent = pHead;

while (pCurrent->pNext)
{
NODE *pTemp = pCurrent->pNext;

if (pCurrent->nValue == pTemp->nValue) //Is duplicate?
{
pCurrent->pNext = pTemp->pNext;
free(pTemp);
}
else
{
pCurrent = pCurrent->pNext;
}
}
}

Display singly-linked list backwards

/*
To print the singly-linked list in reverse order you can
- Reverse the list and then print it. Reverse it back to original form.
- Traverse the list put the content on stack. And then pop and display the contents.
- Use recursive function to display the contents.
*/
void PrintReverseList(NODE *pHead)
{
if (NULL == pHead)
return;

PrintReverseList(pHead->pNext);
printf("\n%d", pHead->nValue);
}

Given two sorted linked lists, write a function to merge them into one.

//This function will merge two sorted linked lists in ascending order.
NODE* MergeSortedList(NODE *pHead1, NODE *pHead2)
{
if ( (NULL == pHead1) && (NULL == pHead2) )
return NULL;

if ( (NULL == pHead1) && (NULL != pHead2) )
return pHead2;

if ( (NULL != pHead1) && (NULL == pHead2) )
return pHead1;

NODE *pNewHead = NULL;
NODE *pCurrent1 = NULL;
NODE *pCurrent2 = NULL;

//Assign new head pointer and initialize pointers
if (pHead1->nValue < pHead2->nValue)
{
pNewHead = pHead1;
pCurrent1 = pHead1;
pCurrent2 = pHead2;
}
else
{
pNewHead = pHead2;
pCurrent1 = pHead2;
pCurrent2 = pHead1;
}

while (pCurrent1 && pCurrent2)
{
if (NULL == pCurrent1->pNext)
{
pCurrent1->pNext = pCurrent2;
break;
}
else
{
if ((pCurrent1->pNext)->nValue < pCurrent2->nValue)
{
pCurrent1 = pCurrent1->pNext;
}
else
{
NODE *pTemp1 = pCurrent1->pNext;
NODE *pTemp2 = pCurrent2->pNext;

pCurrent1->pNext = pCurrent2;
pCurrent2->pNext = pTemp1;

pCurrent1 = pCurrent2;
pCurrent2 = pTemp2;
}
}
} // while

return pNewHead;
}

Leap Year function

bool IsLeapYear(int nYear)
{
if ( (0 == (nYear%4)) && ( (0 != (nYear%100) ) || (0 == (nYear%400) ) ) )
return true;

return false;
}

Given only a pointer to a node to be deleted in a singly linked list, how do you delete it?

/*
- Copy the contents of the node following the node that is provided to the provided node.
- Delete the node following the provided node.

Solution doesn't work if the node that is provided is the last node of the singly-linked list.
*/

bool DeleteNode(NODE *pNode)
{
if ( (NULL == pNode) || (NULL == pNode->pNext) ) //make sure it is not the last node
return false;

NODE *pNext = pNode->pNext;

//Copy contents
pNode->nValue = pNext->nValue;
pNode->pNext = pNext->pNext;

//Delete
free(pNext);

return true;
}

Return Nth the node from the end of the singly-linked list

NODE* FindNthNodeFromEnd(NODE *pHead, int nValue)
{
//Validate input
if ( (NULL == pHead) || (1 > nValue) )
return NULL;

NODE *pLead = pHead; //Move lead pointer to Nth node

int ii = 0;

for (; ii < nValue; ii++)
{
pLead = pLead->pNext;

if (NULL == pLead)
break;
}

if (NULL == pLead)
{
if ( (nValue-1) == ii)
{
return pHead; //head node is the nth node from the end-of-list
}
else
{
return NULL; //the list is smaller than N nodes
}
}

NODE *pFollow = pHead; //Follow pointer follows from a distance of N nodes

//Move both pointers until pLead reaches end-of-list
while (pLead)
{
pLead = pLead->pNext;
pFollow = pFollow->pNext;
}

return pFollow;
}

Toggling case of characters of a string

//Toggle String Case - Convert upper to lower case and vice versa
bool IsLowerCh(char ch)
{
if ( ('a' <= ch) && ('z' >= ch) )
return true;

return false;
}

bool IsUpperCh(char ch)
{
if ( ('A' <= ch) && ('Z' >= ch) )
return true;

return false;
}

char ToUpperCh(char ch)
{
if ( ('a' <= ch) && ('z' >= ch) ) //only if a lower case
return ( 'A' + (ch - 'a') );

return ch;
}

char ToLowerCh(char ch)
{
if ( ('A' <= ch) && ('Z' >= ch) ) //only if a upper case
return ( 'a' + (ch - 'A') );

return ch;
}

void ToggleStringCase(char *pszString)
{
if (NULL == pszString)
return;

while (*pszString)
{
if (IsLowerCh(*pszString))
*pszString = ToUpperCh(*pszString);
else
if (IsUpperCh(*pszString))
*pszString = ToLowerCh(*pszString);

++pszString;
}
}

String case conversion functions

//Converts a string to uppercase string
void ToUpper(char *pszString)
{
if (NULL == pszString)
return;

while (*pszString)
{
if ( ('a' <= *pszString) && ('z' >= *pszString) )
*pszString = 'A' + (*pszString - 'a');

++pszString;
}
}

//Converts a string to lowercase string
void ToLower(char *pszString)
{
if (NULL == pszString)
return;

while (*pszString)
{
if ( ('A' <= *pszString) && ('Z' >= *pszString) )
*pszString = 'a' + (*pszString - 'A');

++pszString;
}
}

Write, efficient code for extracting unique elements from a sorted list of array. e.g. (1, 1, 3, 3, 3, 5, 5, 5, 9, 9, 9, 9) -> (1, 3, 5, 9).

//Removes duplicates, returns the length of the new array
int RemoveDuplicates(int *pArray, int nSize)
{
if ( (NULL == pArray) || ( 0 > nSize) )
return 0;

int CurrentValue = pArray[0];
int CurrentPos = 1;
int InsertPos = 1;

for (; CurrentPos < nSize; CurrentPos++)
{
if (pArray[CurrentPos] != CurrentValue)
{
pArray[InsertPos] = pArray[CurrentPos];
CurrentValue = pArray[CurrentPos];
++InsertPos;
}
}

return InsertPos;
}

Given an array of characters which form a sentence of words, give an efficient algorithm to reverse the order of the words (not characters) in it.

//Idea here is to reverese the entire sentence, then reverse each word in it.
char* ReverseWords(char *pszString)
{
if (NULL == pszString)
return NULL;

char* pTemp = pszString;

//Reverse string
char *pLeft = pTemp;
char *pRight = pTemp;

//Find out the end of sentence
while (*pRight)
{
++pRight;
}

--pRight;

//Reverse sentence
while (pLeft < pRight)
{
char ch = *pLeft;
*pLeft = *pRight;
*pRight = ch;

++pLeft;
--pRight;
}

//Reverse words
while (*pTemp)
{
while ( (*pTemp == ' ') && (*pTemp) )
++pTemp;

pLeft = pTemp;

while ( (*pTemp != ' ') && (*pTemp) )
++pTemp;

pRight = pTemp - 1;

while (pLeft < pRight)
{
char ch = *pLeft;
*pLeft = *pRight;
*pRight = ch;

++pLeft;
--pRight;
}
}

return pszString;
}