Merging two lists as one

This is a discussion on Merging two lists as one within the C++ Programming forums, part of the General Programming Boards category; I'm writing the classic merge sort, but with a linked list rather than arrays (strings are the element being sorted, ...

  1. #1
    Registered User
    Join Date
    Sep 2004
    Posts
    12

    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. #2
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    712
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. merging linked lists
    By scwizzo in forum C++ Programming
    Replies: 15
    Last Post: 09-14-2008, 06:07 PM
  2. Help With Merging Sorted Lists of Strings
    By genjiguy in forum C++ Programming
    Replies: 3
    Last Post: 04-14-2005, 04:53 PM
  3. Linked Lists 101
    By The Brain in forum C++ Programming
    Replies: 5
    Last Post: 07-24-2004, 05:32 PM
  4. merging two linked lists..
    By Makimura in forum C++ Programming
    Replies: 2
    Last Post: 11-14-2001, 12:34 PM
  5. Merging Linked Lists
    By Unregistered in forum C++ Programming
    Replies: 3
    Last Post: 09-23-2001, 08:08 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21