Combing two linked lists

Discussion in 'C++' started by deanfamily, Dec 7, 2005.

  1. deanfamily

    deanfamily Guest

    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?
    deanfamily, Dec 7, 2005
    #1
    1. Advertising

  2. deanfamily wrote:
    > 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.
    Neelesh Bodas, Dec 7, 2005
    #2
    1. Advertising

  3. deanfamily

    Marcus Kwok Guest

    deanfamily <> wrote:
    > 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?

    --
    Marcus Kwok
    Marcus Kwok, Dec 7, 2005
    #3
  4. Marcus Kwok wrote:
    >
    > 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" ;-)
    Neelesh Bodas, Dec 7, 2005
    #4
  5. deanfamily

    Andre Kostur Guest

    "Neelesh Bodas" <> wrote in
    news::

    >
    > Marcus Kwok wrote:
    >>
    >> 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" ;-)


    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...)
    Andre Kostur, Dec 7, 2005
    #5
  6. * 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::eek: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::eek: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 ) );
    }

    --
    A: Because it messes up the order in which people normally read text.
    Q: Why is it such a bad thing?
    A: Top-posting.
    Q: What is the most annoying thing on usenet and in e-mail?
    Alf P. Steinbach, Dec 7, 2005
    #6
  7. deanfamily

    Rolf Magnus Guest

    Andre Kostur wrote:

    >>> 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" ;-)

    >
    > 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.
    Rolf Magnus, Dec 7, 2005
    #7
  8. "deanfamily" <> wrote:

    > 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.)


    --
    Robbie Hatley
    lone wolf intj at pac bell dot net
    Robbie Hatley, Dec 7, 2005
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Chris Ritchey
    Replies:
    7
    Views:
    463
    emerth
    Jul 10, 2003
  2. Chris Ritchey

    Generating a char* from a linked list of linked lists

    Chris Ritchey, Jul 9, 2003, in forum: C Programming
    Replies:
    7
    Views:
    453
    emerth
    Jul 10, 2003
  3. jawdoc
    Replies:
    9
    Views:
    734
    Chris Thomasson
    Mar 10, 2008
  4. Will

    Combing html and server controls

    Will, Aug 2, 2008, in forum: ASP .Net
    Replies:
    1
    Views:
    273
    bruce barker
    Aug 2, 2008
  5. Replies:
    2
    Views:
    258
    kirby urner
    Dec 15, 2010
Loading...

Share This Page