# Thread: Merging two lists as one

1. ## Merging two lists as one

I'm writing the classic merge sort, but with a linked list rather than arrays (strings are the element being sorted, s is the variable used). I'm having problems writing the method that merges two sorted lists together. The 'this' Node is the head of the first list and 'o' points to the head of the second list. I've commented most of the lines below, including the spots where I'm confused on syntax.

Code:
Node *Node::merge(Node *o) {
if (o == NULL) return this;            //if second list doesn't exist, return this, as there is only the first list and it's already sorted
else {
if (this->s <= o->s) {        //item in first list goes before item in second list
if (next != NULL) next = next->merge(o); //checks the next item in the first list with first item in the second list
else return next->o;      //?? on syntax, I want to attach the head of the second list to the last Node in the first list, but with this code I'm getting a compiler error stating that 'o' doesn't exist.
//How would I do this?

}

else {                           //item in second list goes before item in first list
Node *temp = o->next;  //temporary pointer to the next item in second list
o->next = this;   //now points head of second list to head of first list
if (o->next != NULL) return next = next->merge(temp);
else return o->this;
}

}

}
I'm mainly confused on the second part of the method, how to switch around the pointers on the two lists. Any help or suggestion s would be great.
Also, I apologize in advance in my comments are confusing; to be truthful I'm much better at explaining what my code means in speech as compared to text.

2. I have working recursive implementation
Code:
node * merge(node * list1, node * list2)
{
if (list1 == NULL)
return list2;
if (list2 == NULL)
return list1;
if (list1->data < list2->data)
{
list1->next = merge(list1->next, list2);
return list1;
}
else
{
list2->next = merge(list1, list2->next);
return list2;
}
}
I hope this helps.