Merging two sorted single linked lists

#include < iostream >
using namespace std;
struct Node
{
Node* Next;
int val;
};

void InsertNode(Node** pNode, int val)
{
if(pNode == NULL)
return;
Node * pTemp, *pTraversal;
pTraversal = *pNode;
pTemp = new Node();
pTemp->val = val;
pTemp->Next = NULL;
if(*pNode == NULL)
{
*pNode = pTemp;
return;
}
while(pTraversal->Next != NULL)
{
pTraversal = pTraversal->Next;
}
pTraversal->Next = pTemp;

return;
}
void Display(Node* pNode)
{
while(pNode != NULL)
{
cout < < pNode->val < < " ";
pNode = pNode->Next;
}
}

void MergeLL(Node* pNodeIP1,Node* pNodeIP2, Node** ppNodeOP)
{
Node * pTemp = NULL;

while((pNodeIP1 != NULL)&&(pNodeIP2 != NULL))
{
if(pNodeIP1->val <= pNodeIP2->val)
{
if(*ppNodeOP == NULL)
{
*ppNodeOP = pNodeIP1;
pTemp = *ppNodeOP;
}
else
{
pTemp->Next = pNodeIP1;
pTemp = pTemp->Next;
}
pNodeIP1 = pNodeIP1->Next;
pTemp->Next = NULL;
}
else
{
if(*ppNodeOP == NULL)
{
*ppNodeOP = pNodeIP2;
pTemp = *ppNodeOP;
}
else
{
pTemp->Next = pNodeIP2;
pTemp = pTemp->Next;
}
pNodeIP2 = pNodeIP2->Next;
pTemp->Next = NULL;
}

}
if(pNodeIP2 == NULL)
pTemp->Next = pNodeIP1;
if(pNodeIP1 == NULL)
pTemp->Next = pNodeIP2;
}
int _tmain(int argc, _TCHAR* argv[])
{
Node* HeadOfList1 = NULL;
InsertNode(&HeadOfList1,1);
InsertNode(&HeadOfList1,3);
InsertNode(&HeadOfList1,5);
InsertNode(&HeadOfList1,7);
InsertNode(&HeadOfList1,11);
InsertNode(&HeadOfList1,13);
InsertNode(&HeadOfList1,15);

Node* HeadOfList2 = NULL;
InsertNode(&HeadOfList2,2);
InsertNode(&HeadOfList2,4);
InsertNode(&HeadOfList2,6);
InsertNode(&HeadOfList2,7);
InsertNode(&HeadOfList2,8);
InsertNode(&HeadOfList2,10);

cout < < "Contents of Sorted List1 :";
Display(HeadOfList1);

cout < < "\nContents of Sorted List2 :";
Display(HeadOfList2);

Node* HeadOfList3 = NULL;
MergeLL(HeadOfList1,HeadOfList2,&HeadOfList3);
cout < < "\nContents of Merged Sorted List :";
Display(HeadOfList3);
return 0;
}

Binary Tree -Depth First Traversal - Recursive / Non Recursive

#include "stdafx.h"
#include < iostream >
#include < stack >
using namespace std;
struct Node{
Node* Left;
Node* Right;
int Val;
};
void InsertNode(Node** ppNode,int val)
{
if(ppNode == NULL)
return;
if(*ppNode == NULL)
{
*ppNode = new Node();
(*ppNode)->Val = val;
(*ppNode)->Left = (*ppNode)->Right = NULL;
}
else
{
if(val > (*ppNode)->Val)
InsertNode(&((*ppNode)->Right),val);
else
InsertNode(&((*ppNode)->Left),val);
}
}
void PreOrderRecursive(Node* pNode)
{
cout<<" "<Val;
if(pNode->Left)
PreOrderRecursive(pNode->Left);
if(pNode->Right)
PreOrderRecursive(pNode->Right);
}
void PreOrderNonRecursive(Node* pNode)
{
bool done;
stacks;
Node * cursor = pNode;
done = false;

while(!done)
{
if(cursor != NULL)
{
cout<<" "<Val;
s.push(cursor);
cursor = cursor->Left;
}
else
{
if(!s.empty())
{
cursor = s.top();
s.pop();
cursor = cursor->Right;
}
else
{
done = true;
}
}
}
}
void InOrderRecursive(Node* pNode)
{
if(pNode->Left != NULL)
InOrderRecursive(pNode->Left);
cout<<" "<Val;
if(pNode->Right != NULL)
InOrderRecursive(pNode->Right);
}

void InOrderNonRecursive(Node* pNode)
{
bool done;
stack s;

Node* cursor = pNode; //set cursor to root of binary tree
done = false;

while (!done)
{
if(cursor != NULL)
{
s.push(cursor); //place pointer to node on the stack
//before traversing the node's left subtree
cursor = cursor->Left; //traverse the left subtree
}
else //backtrack from the empty subtree and
//visit the node at the top of the stack;
//however, if the stack is empty, you are
//done
{
if (!s.empty())
{
cursor = s.top();
s.pop();
cout <<" "<Val;
cursor = cursor->Right;
}
else
done = true;
}
}


}
void PostOrderRecursive(Node* pNode)
{
if(pNode->Left != NULL)
PostOrderRecursive(pNode->Left);
if(pNode->Right != NULL)
PostOrderRecursive(pNode->Right);
cout<<" "<Val;
}

int _tmain(int argc, _TCHAR* argv[])
{
Node* Head = NULL;
InsertNode(&Head,6);
InsertNode(&Head,4);
InsertNode(&Head,5);
InsertNode(&Head,2);
InsertNode(&Head,3);
InsertNode(&Head,1);
InsertNode(&Head,8);
InsertNode(&Head,7);
InsertNode(&Head,9);
cout< < "Recursive Inorder Traversal :";
InOrderRecursive(Head);
cout< < endl < < "Non recursive Inorder Traversal :";
InOrderNonRecursive(Head);
cout< < endl < <"Recursive Preorder Traversal :";
PreOrderRecursive(Head);
cout< < endl < < "Non recursive Preorder Traversal :";
PreOrderNonRecursive(Head);
cout< < endl < < "Recursive Postorder Traversal :";
PostOrderRecursive(Head);
return 0;
}

Find the first unique charater in a string.

#include <>
using namespace std;
int FindFirstUniqueChar(char* szString,char* uniqueChar)
{
if((szString == NULL) (uniqueChar == NULL))
return -1;
int indexPos[257];
int count[257];
char* temp = szString;
memset(uniqueChar,0,(sizeof(uniqueChar)/sizeof(&uniqueChar[0])));
memset(count,0,257*sizeof(int));
memset(indexPos,-1,257*sizeof(int));
while(*temp)
{
count[*temp]++;
if( indexPos[*temp] == -1)
indexPos[*temp] = (temp - szString);
temp++;
}
int idx = 256;
for(int i = 0; i < 257; i++)
{
if((indexPos[i] <= idx) && (count[i] == 1))
{
*uniqueChar = char(i);
*(uniqueChar+1) = '\0';
idx = i;
}
}
if((idx != 256) && (*uniqueChar != NULL))
{
return 0;
}
return -2;
}
int main ()
{
char ch[2];
int ret = FindFirstUniqueChar("tomato",ch);
return 0;
}

Finding if a character is present in a string

Finding if a character is present in a string
#include "stdafx.h"
#include <>
#include <>
#include <>
using namespace std;
bool CheckCharPresent(_TCHAR *str,_TCHAR ch)
{
if((str == NULL)(ch == NULL))
return false;
_TCHAR *ptr = str;
for(unsigned i = 0; i < _tcslen(str); i++)
{
if(ptr[i] == ch)
return true;
}
return false;
}


int _tmain(int argc, _TCHAR* argv[])
{
bool val = CheckCharPresent(_TEXT("Rajesh"),_TEXT('h'));
val = CheckCharPresent(_TEXT("h"),NULL);
val = CheckCharPresent(NULL,_TEXT('h'));
return 0;
}

BruteForce Algorithm - finding a substring in a string

void BruteForceAlgo(char * szString, int iLenString, char* szPattern, int iLenPattern)
{
int i, j;
for(i = 0; i <= (iLenString - iLenPattern); i++)
{
for(j = 0; j < iLenPattern;)
{
if(szString[i+j] == szPattern[j])
j++;
else break;
}
if(j == iLenPattern)
printf("Pattern found at position %d\n",i+1);

}
}
int main(int argc, char* argv[])
{
BruteForceAlgo("HotalHotelHotalHotel", 20,"Hotel",5);
printf("\n%d\n", atoi_CustomImplementation("-1998"));
return(0);
}