Combining two lists

[iamthesgt]

This is homework. I am not asking for someone to write this code for me, just to help me understand how to solve my problem.

I have to take two lists or integers inputted by the user, sorted in ascending order and combine them using pass-by-reference to return a pointer to the head of a new list that contains all the values from the first list, now sorted in ascending order together. Ex: List A contains 3,5,6,10; List B contains 1,4,5,7,10,11. The resultant list should output 1,3,4,5,5,6,7,10,10,11.

I am very new at lists, and don't quite understand them fully but what I want to do for the merge_list function is this (this is kind of pseudocode, as I am trying to convert it to real code. This is what I need the most help on):

int list1counter;
int list2counter
while (list1counter < list1size)
{
      if(list1value>list2value)
      {
         if (list1value<list2value_at_next_position)
         {
            insert_here(list1value);
            list1counter++;
         }
         else
         {
             list2counter++;
         }
      else
      {
          if(top_of_list)
          {
             head_insertl2(list1value);
          }
          else
          {
              cout << "error; value processed improperly";
              return 0;
          }
      }
}

I defined my pointers like so:

typedef s1* s1p;
s1p *iter;

I started using an iterator to cycle through but I'm not sure how it will work since I have to cycle through two lists basically simultaneously. The iterator currently looks like for(iter = head1; iter != NULL; iter = iter->link) .

My insert function:

int insert_here(s1p after_me, int numins)
{
    s1p temporary;
    temporary = new Node;
    
    temporary->data = numins;
    
    temporary->link = after_me->link;
    after_me->link = temporary;
}

Basically I'm not sure how to use the iterator to cycle through both lists and compare the values at both positions. If anyone could give some pointers (no pun intended), that would be great.

[gerard4143]

The container list has a merge member function, I would look up its functionality.

http://www.cplusplus.com/reference/stl/list/merge/

[arkoenig]

Don't use a for statement. The trouble with for statements is that they push you in the direction of iterating over a single range of values, and the problem you're trying to solve involves iterating over two ranges of values at once.

What you want to do is have two iterators, each marking a place in one of the input lists. Now you want to repeat the following steps:

1) If both iterators are at the ends of their respective lists, you're done.

2) If one iterator is at the end of its list and the other isn't, copy to the output the element to which the iterator refers that's not off the end; then increment that iterator.

3) If you got here, then neither iterator is at the end of its list. Therefore, both iterators refer to elements. Compare the elements, copy the smaller of the two to the output, and increment the corresponding iterator.

[iamthesgt]

How do you use an iterator? Out textbook told us to use them like:

struct structure
{
//some declarations
};

typedef structure* structpoint;
structpoint *iter;

for (iter = head; iter != NULL; iter = iter->link) //where head is the head of the list

I don't see how to use two of the simultaneously.

[arkoenig]

You can use iterators without using a "for" statement.

My earlier remarks show you exactly what you need to do.

I can't be more specific because (a) You haven't been specific about what data structures you're using, and (b) If I were, I would be doing your homework for you.

[iamthesgt]

So use a while loop?

while (head_list1 != NULL)
{
while (head_list2 != NULL)
{
//code here
}
}

And I can't copy the elements, the function must return a pointer to the third list (output list).

[arkoenig]

Sorry, no more hints. I've already told you all you need to know.

[iamthesgt]

I got all my code working except my merge function. This may be a piddly error, but I cannot figure out what is wrong.

void merge_lists(Node head, Node head2)
{
  Node result;
  Node *point = &result;

  while (head != NULL && head2 != NULL)
    {
      if (head->data < head2->data)
	{
	  point->next = head;
	  head = head->next;
	}
      else
	{
	  point->next = head2;
	  head2 = head2->next;
	}
    }
}

When compiled (using the g++ compiler on ubuntu 10.04), I get a bunch of Node errors:
sumnerassg17feb.cpp: In function ‘void merge_lists(Node, Node)’:
sumnerassg17feb.cpp:3: error: no matching function for call to ‘Node::Node()’
sumnerassg17feb.cpp:: note: candidates are: Node::Node(int, Node*)
sumnerassg17feb.cpp:: note: Node::Node(const Node&)
sumnerassg17feb.cpp:6: error: no match for ‘operator!=’ in ‘head != 0l’
sumnerassg17feb.cpp:6: error: no match for ‘operator!=’ in ‘head2 != 0l’
sumnerassg17feb.cpp:8: error: base operand of ‘->’ has non-pointer type ‘Node’
sumnerassg17feb.cpp:8: error: base operand of ‘->’ has non-pointer type ‘Node’
sumnerassg17feb.cpp:10: error: cannot convert ‘Node’ to ‘Node*’ in assignment
sumnerassg17feb.cpp:11: error: base operand of ‘->’ has non-pointer type ‘Node’
sumnerassg17feb.cpp:15: error: cannot convert ‘Node’ to ‘Node*’ in assignment
sumnerassg17feb.cpp:16: error: base operand of ‘->’ has non-pointer type ‘Node’

I don't know why my pointers are not working. Can anyone tell me why or at least give me a helpful hint? Thanks.

[gerard4143]

The errors are pretty self explanatory. Line 3 - you don't have a default constructor for node, line 6 - node doesn't have an operator !=...etc.

[iamthesgt]

I figured it out - line 1 should read void merge_lists([U]NodePointer [/U]head, [U]NodePointer [/U]head2) .
Before, i was using type Node instead of NodePointer, and so the function was being called improperly in the main function.
However, now I get a new error:
"[Linker error] undefined reference to `Node::Node()' Id returned 1 exit status"
Does anybody know why this is?

[gerard4143]

Calling this

Node result;

requires node to have a default constructor.

[iamthesgt]

It does. In my program, the class is defined as follows:

class Node
{
      public:
         int data;
         Node* next;
         Node();
         Node (int x, Node* y)
         {
              data = x;
              next = y;
         }
};

[gerard4143]

It does. In my program, the class is defined as follows:

class Node
{
      public:
         int data;
         Node* next;
         Node();
         Node (int x, Node* y)
         {
              data = x;
              next = y;
         }
};

What you posted is a declaration of Node::Node() not a definition.

[iamthesgt]

How do you declare Node:Node() then? I thought a default constructor was merely a constructor with no arguments.

EDIT:
Never mind, I figured it out. In my class, it should be defined like:

Node()
         {
         data = 0;
         next = NULL;
         }