Combing two linked lists

[deanfamily]

Here's the problem:
I have two linked lists of integers (list1 and list2) that are already in
sequential order, and I need to combine them into one list in sequential
order (newList). Any thoughts?

 

[Neelesh Bodas]

Here's the problem:
I have two linked lists of integers (list1 and list2) that are already in
sequential order,

What do you mean by "sequencial order" of a linked list?

and I need to combine them into one list in sequential

order (newList). Any thoughts?

Use std::list instead of using raw linked lists(unless this is a
homework, in which case, look up the FAQ 5.2.

 

[Marcus Kwok]

Here's the problem:
I have two linked lists of integers (list1 and list2) that are already in
sequential order, and I need to combine them into one list in sequential
order (newList). Any thoughts?

Yes, I would use a merge sort. But what is your C++ question?

 

[Neelesh Bodas]

Yes, I would use a merge sort. But what is your C++ question?

Oh, to be precise, you meant you would you the procedure "merge", not
the merge "sort" ;-)

 

[Andre Kostur]

Oh, to be precise, you meant you would you the procedure "merge", not
the merge "sort" ;-)

No, I would create a mergeSort function which takes as input 2 lists, and
outputs a third list containing the sorted aggregate of the 2 input lists.
(Although I'd first look to see of the Standard library already has one...
I don't recall off the top of my head. Then again, merge sort is a pretty
easy algorithm...)

 

[Alf P. Steinbach]

* deanfamily:

Here's the problem:
I have two linked lists of integers (list1 and list2) that are already in
sequential order, and I need to combine them into one list in sequential
order (newList). Any thoughts?

#include <algorithm> // std::copy
#include <iterator> // std:stream_iterator
#include <iostream> // std::cout
#include <ostream> // <<, std::endl
#include <memory> // std::auto_ptr
#include <list> // std::list

typedef std::list<int> IntList;
typedef std::auto_ptr<IntList> IntListAutoPtr;

void display( IntList const& list )
{
std:stream_iterator<int> out( std::cout, " " );
std::copy( list.begin(), list.end(), out );
std::cout << std::endl;
}

void moveToTailOf( IntList& left, IntList& right )
{
left.splice( left.end(), right );
}

IntListAutoPtr destructiveConcat( IntList& left, IntList& right )
{
IntListAutoPtr result( new IntList );

moveToTailOf( *result, left );
moveToTailOf( *result, right );
return result;
}

IntListAutoPtr concat( IntList const& left, IntList const& right )
{
IntList copyOfLeft( left );
IntList copyOfRight( right );
return destructiveConcat( copyOfLeft, copyOfRight );
}

int main()
{
IntList a, b;

for( int x = 1; x <= 3; ++x ) { a.push_back( x ); }
for( int x = 101; x <= 103; ++x ) { b.push_back( x ); }

display( a );
display( b );
display( *concat( a, b ) );
}

 

[Rolf Magnus]

No, I would create a mergeSort function which takes as input 2 lists, and
outputs a third list containing the sorted aggregate of the 2 input lists.
(Although I'd first look to see of the Standard library already has one...

It actually does. std::merge() in <algorithm> is exactly that.

 

[Robbie Hatley]

I have two linked lists of integers (list1 and list2) that are already in
sequential order, and I need to combine them into one list in sequential
order (newList). Any thoughts?

std::list<int> list1;
std::list<int> list2;

(put stuff in lists)

list1.sort(); // Must do this before merging
list2.sort(); // Must do this before merging

list1.merge(list2); // Merges and sorts.

(At this point, list2 is now empty; it's former members have
now all been sort-merged into list1.)