#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;
}
Tuesday, November 25, 2008
Subscribe to:
Post Comments (Atom)
.jpg)
No comments:
Post a Comment