 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
deanfamily
Guest
|
 Posted: Wed Dec 07, 2005 3:06 pm Post subject: Combining two linked lists |
 |
|
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?
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
 |
Kodt
Guest
|
| Posted: Wed Dec 07, 2005 6:51 pm Post subject: Re: Combining two linked lists |
|
|
deanfamily wrote:
| Quote: | 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?
|
1) Algorithm. It is very simple
V1
While both lists are not empty
- peek heads of both lists and compare them
- remove the smaller value from its list and push back into the output.
Finally, when one list becomes empty, append the other to the output.
V2
Like V1, but use sequential iterators instead of dropping items from
the lists.
"Peek a head" => dereferensing the iterator, and "remove" => moving one
step forth.
V3
Let the first list be our output. (If we should keep inputs unchanged,
just copy it).
As in V2, we'll slide iterators forward.
"Push back" from the first list to the output (that is, to itself) =>
just go forth
"Push back" from the second list to the output => insert before.
2) Implementation.
It depends on your data structures, and on a requirement: can we
destroy inputs (building the output from their parts) or just read them
and copy data.
For example, your lists are std::list.
V1 (destructive)
std::list a, b; // inputs
std::list c; // output
while(!a.empty()&&!b.empty())
if(a.front() < b.front())
{ c.push_back(a.front()); a.pop_front(); }
else
{ c.push_back(b.front()); b.pop_front(); }
c.append(a); c.append(b); // in fact, only one of them - because the
other is empty
V2
// same vars as above, and...
std::list::const_iterator ia=a.begin(), ib=b.begin();
while(ia!=a.end() && ib!=b.end())
c.push_back( ((*ia < *ib) ? ia : ib)++ );
c.append(a); c.append(b); // in fact, only one of them - because the
other is empty
For example, your lists are single-linked lists like that
struct Node { int data; Node* next; }; // next==NULL means the node is
last
V1 (destructive)
Node *a, *b; // also they are iterators to the lists
Node *c;
// to efficiently push back, we should remember the pointer to the last
node... or even pointer-to-pointer
Node **e;
c = NULL; // initially the output is empty
e = &c; // first time we'll write to the variable 'c'; then, to some
node's 'next'
while(a && b)
{
if(*a < *b)
{ *e = a; a = a->next; } // attach the head of a to *e, and shift
else
{ *e = b; b = b->next; }
e = &((*e)->next);
*e = NULL; // this is not mandatory - just to keep the output list in
good health
}
// append the rest
if(a)
*e = a;
else // even if b is empty: in this case we just write NULL to the
final 'next' pointer
*e = b;
Of course, the code above is just for illustration. There may be some
subtle questions of copying/moving data, checking integrity (for
example: what happens if we try to merge a list with itself) and so on.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Jeff Flinn
Guest
|
| Posted: Wed Dec 07, 2005 11:26 pm Post subject: Re: Combining two linked lists |
|
|
"Kodt" <nickolay.merkin (AT) gmail (DOT) com> wrote
| Quote: | 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?
1) Algorithm. It is very simple
|
....
These are std::list's right?  Why not use std::list::merge? Otherwise
std::merge.
Jeff Flinn
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Thomas Tutone
Guest
|
| Posted: Thu Dec 08, 2005 11:48 am Post subject: Re: Combining two linked lists |
|
|
deanfamily wrote:
| Quote: | 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?
|
std::list<int> newList(list1);
newList.merge(list2);
Note that list2 will be empty after this - copy it first if you need to
keep it.
Best regards,
Tom
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
KoKoCrunch
Guest
|
| Posted: Thu Dec 08, 2005 11:49 am Post subject: Re: Combining two linked lists |
|
|
If you are using std::list and both list are sorted you can use
std::merge in <algorithm>
for example:
std::list<int> l1;
std::list<int> l2;
std::list<int> mergedList;
l1.push_back(1);
l1.push_back(2);
l1.push_back(3);
l2.push_back(0);
l2.push_back(2);
l2.push_back(3);
l2.push_back(4);
std::merge(l1.begin(), l1.end(), l2.begin(), l2.end(),
std::back_inserter(mergedList));
std::copy(mergedList.begin(), mergedList.end(),
std::ostream_iterator<int>(std::cout, " "));
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
