Jump to content


Check out our Community Blogs

Register and join over 40,000 other developers!


Recent Status Updates

View All Updates

Photo
- - - - -

[SOLVED] Sorted Merge Of A Linked List

linked list

  • This topic is locked This topic is locked
5 replies to this topic

#1 Cheung

Cheung

    CC Lurker

  • New Member
  • Pip
  • 5 posts

Posted 27 April 2012 - 02:59 PM

Hi, this is my first post, and probably the start of many as I will be taking Computer Science courses all throughout college.

I'm currently stuck on this problem:

// merges (by simple interleaving) first and second lists to create
// a new list - - copies the nodes, and does not change parameter lists
Node *sortedMerge(Node* &first, Node* &second) {


And here's the constructor:
struct Node {
int data;
Node* next;

// constructor implemented here ("implicit inline")
Node (int item, Node* n = 0) : data(item), next(n) { }
};



My attempt:


Node *sortedMerge(Node* &first, Node* &second) {

Node* locationl1;
Node* locationl2;
Node* result;

locationl1 =new Node(first->data);
locationl2 =new Node(second->data);
if(locationl1 < locationl2)
{result=locationl1;
result->next=locationl2;
result=result->next;
}
else
{
result=locationl2;
result->next=locationl1;
result=result->next;
}


while (locationl1->next && locationl2->next != NULL)
{
if(locationl1 && locationl2 == NULL)break;
if(locationl1->data < locationl2->data)
{
result->next=locationl1;
result=result->next;
result->next=locationl2;
result=result->next;
}
else if(locationl1->data > locationl2->data)
{
result->next=locationl2;
result=result->next;
result->next=locationl1;
result=result->next;
}
locationl1=locationl1->next;
locationl2=locationl2->next;
}
return result;

}


The problem that I am running is to is looping through lists first and second without messing up those lists. Any help appreciated.
  • 0

#2 Cheung

Cheung

    CC Lurker

  • New Member
  • Pip
  • 5 posts

Posted 27 April 2012 - 04:11 PM

K, got to this, still not working though, but this is a bit closer to expected results:


Node* locationl1;
Node* locationl2;
Node* result;
Node* firstholder=first;
Node* secondholder=second;
Node* resultholder;
locationl1 =new Node(first->data);
locationl2 =new Node(second->data);
if(locationl1 > locationl2)
{resultholder=locationl1;
result=resultholder;
firstholder=firstholder->next;
}
else
{
resultholder=locationl2;
result=resultholder;
secondholder=secondholder->next;
}
resultholder=resultholder->next;

while (firstholder->next && secondholder->next != NULL)
{
if(firstholder && secondholder == NULL)break;
if(firstholder->data > secondholder->data)
{
resultholder->next=secondholder;
resultholder=resultholder->next;
secondholder=secondholder->next;
}
else// (firstholder->data > secondholder->data)
{
resultholder->next=firstholder;
resultholder=resultholder->next;
firstholder=firstholder->next;
}
}
return result;

Made some slight changes again

Node* locationl1;
Node* locationl2;
Node* result;
Node* firstholder=first;
Node* secondholder=second;
Node* resultholder;
locationl1 =new Node(first->data);
locationl2 =new Node(second->data);
if(locationl1 > locationl2)
{resultholder=locationl1;
result=resultholder;
firstholder=firstholder->next;
}
else
{
resultholder=locationl2;
result=resultholder;
secondholder=secondholder->next;
}

while (firstholder->next && secondholder->next != NULL)
{
if(firstholder->data > secondholder->data)
{
resultholder->next=new Node(secondholder->data);
resultholder=resultholder->next;
secondholder=secondholder->next;
}
else
{
resultholder->next=new Node(firstholder->data);
resultholder=resultholder->next;
firstholder=firstholder->next;
}
}
return result;
  • 0

#3 Cheung

Cheung

    CC Lurker

  • New Member
  • Pip
  • 5 posts

Posted 27 April 2012 - 04:34 PM

Finished.

Final code:

Node *sortedMerge(Node* &first, Node* &second) {

Node* locationl1;
Node* locationl2;
Node* result;
Node* firstholder=first;
Node* secondholder=second;
Node* resultholder;
locationl1 =new Node(first->data);
locationl2 =new Node(second->data);
if(locationl1 > locationl2)
{resultholder=locationl1;
result=resultholder;
firstholder=firstholder->next;
}
else
{
resultholder=locationl2;
result=resultholder;
secondholder=secondholder->next;
}

while (firstholder && secondholder != NULL)
{
if(firstholder && secondholder == NULL) break;
if(firstholder->data > secondholder->data)
{
resultholder->next=new Node(secondholder->data);
resultholder=resultholder->next;
secondholder=secondholder->next;
}
else if(firstholder->data < secondholder->data)
{
resultholder->next=new Node(firstholder->data);
resultholder=resultholder->next;
firstholder=firstholder->next;
}
}
if(firstholder!=NULL && secondholder ==NULL)
{
while(firstholder!=NULL)
{
if(firstholder==NULL)break;
resultholder->next=firstholder;
resultholder=resultholder->next;
firstholder=firstholder->next;
}
}
if(secondholder!=NULL && firstholder==NULL)
{
while(secondholder!=NULL)
{
if(secondholder==NULL)break;
resultholder->next=secondholder;
resultholder=resultholder->next;
secondholder=secondholder->next;
}
}

return result;

}

There are definitely more efficient ways to write this. But I don't know enough C++ Syntax to do so. And/or, my logic sucks.
  • 0

#4 BlackRabbit

BlackRabbit

    CodeCall Legend

  • Expert Member
  • PipPipPipPipPipPipPipPip
  • 3871 posts
  • Location:Argentina
  • Programming Language:C, C++, C#, PHP, JavaScript, Transact-SQL, Bash, Others
  • Learning:Java, Others

Posted 27 April 2012 - 08:39 PM

I just got logged in and see all the develop, i can see you did it quickly and by yourself, you are gonna be a great coder,
when you are starting doing the thing and owning the solution is the best way, you will learn "perfect code" later, it comes with experience

So ... nice work Cheung, keep it up
  • 0

#5 Cheung

Cheung

    CC Lurker

  • New Member
  • Pip
  • 5 posts

Posted 28 April 2012 - 01:31 PM

Thanks BlackRabbit, it means a lot :)
  • 0

#6 Roger

Roger

    Skadoosh!

  • Administrator
  • 1222 posts
  • Programming Language:C, PHP
  • Learning:Others

Posted 03 May 2012 - 12:00 AM

This topic has been marked as SOLVED. If you have a similar topic, please start a new thread and reference this thread to continue discussions.
  • 0

New around here? Click here to register and start participating in under a minute?

Or do a quick search and you may find the answer you're looking for.






Also tagged with one or more of these keywords: linked list

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download