|
-
March 25th, 2012, 07:19 PM
#1
Linked List Problem
Hello. I am supposed to write a program that process a linked list and creates distinct pairs.
For example. a list containing 5 becomes 5 5
5 2 4 5 4 becomes 5 5 2 2 4 4
1 2 3 3 1 3 2 becomes 1 1 2 2 3 3
1 3 1 1 0 4 3 2 0 3 2 2 2 2 3 4 1 1 2 becomes 1 1 3 3 0 0 4 4 2 2
3 0 2 2 2 0 1 5 1 0 0 4 4 1 0 5 becomes 3 3 0 0 2 2 1 1 5 5 4 4
5 5 5 5 2 3 1 3 3 2 3 0 2 4 1 4 becomes 5 5 2 2 3 3 1 1 0 0 4 4
If I pass a list with 5 2 4 5 4 it becomes 5 5 2 2 4 4 but when I pass a list without duplicates like
say 3 4 it will return 33 4. In other words it only creates one duplicate, everything else seems to be working. I would greatly appreciate if anyone could point me in the right direction.
Thank you in advance.
Code:
void CreateDistinctPairs()
{
Node* ourHead = head;
Node* first = head;
Node* prev = head;
bool duplicateFound = false;
while (first->next)
{
while (first)
{
prev = first;
first = first->next;
if ((!duplicateFound) && (first) &&
first->info == ourHead->info) // did we find a duplicate
{
duplicateFound = true;
if (ourHead->next != first) // duplicate not adjacent to ourHead
{
if (first->next != 0) // there is an adjacent node next to duplicate ?
{ // rearrange
prev->next = first->next; // rearrange them
first->next = ourHead->next; // to make duplicates
ourHead->next = first;
if (first->next)
{
prev = first;
first = first->next;
}
}
else
{
prev->next = first->next; // rearrange them
first->next = ourHead->next; // to make duplicates
ourHead->next = first;
first = 0;
}
}
}
if (duplicateFound && ourHead->next != first) // remove remaining duplicates
{
if ((first) && first->info == ourHead->info) // next duplicate found
{ // remove it
Node* nodeToRemove = prev->next;
first = first->next;
prev->next = first;
delete nodeToRemove;
}
}
if(first->next == 0 && (!duplicateFound))
{
Node* duplicate = new Node;
duplicate->info= ourHead->info;
duplicate->next = ourHead->next;
ourHead->next = duplicate;
first = 0;
}
}
duplicateFound = false;
if(ourHead->next->next == 0) break;
else
{
ourHead = ourHead->next->next;
first = ourHead;
}
}
}
Tags for this Thread
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|