efficient way of collating (mixing) two linked lists using C

Do you have a question? Post it now! No Registration Necessary

Translate This Thread From English to

Threaded View
Dear all,
   1)In one of our implementation for an application we are supposed to
collate two linked lists.The actual problem is like this:


There are two singularly linked lists, the final output will be a
"perfectly shuffle" of the lists together into a single list.  The new
list should consist of consecutively alternating nodes  from both
lists.Note that both these linked lists have same kind of data
structure in their nodes.

solution:
The logic which I thought for implementing this is to create temporary
node which resembles the nodes in the input linked lists and then copy
second node into it,swap the pointers to insert the second lists first
node into the first lists second node and proceed so on recursively by
inserting the second lists node in between the first lists node.

Is my thinking correct?I believe this is not that efficient way of
doing it.Can some one let me know how effectively should we implement
this collation between two  linked lists?

2)I came across the following code snippet regarding linked lists:
struct _tagElement
{
       int m_cRef;
       unsigned char m_bData[20];
       struct _tagElement * m_next;

} NODE, * PNODE;

PNODE DoesWhat (PNODE pn1, PNODE pn2)
{
       PNODE * ppnV = &pn1;
       PNODE * ppn1 = &pn1;
       PNODE * ppn2 = &pn2;

       for ( ; *ppn1 || *ppn2; ppn1 =
&((*ppn1)->m_next))
       {
              if (!(*ppn1) || (0 <
memcmp((*ppn1)->m_bData, (*ppn2)->m_bData,
sizeof((*ppn2)->m_bData))))
              {
                     PNODE pn = *ppn1;
                     *ppn1 = *ppn2;
                     pn2 = (*ppn2)->m_next;
                     (*ppn1)->m_next = pn;
              }
       }
       return *ppnV;
}
I inferred from this code,that the actual functionality of the function
"DoesWhat" is to collate two linked list as stated in query (1)
referred in this post.But my friend disagrees.I said that the function
doeswhat takes first node of two linked lists(pn1 is first node of
linkedlist1,pn2 is first node of linkedlist2-This is my assumption(need
not be correct!)),and the code inside inserts nodes of list2 into nodes
of list1,also the list will be sorted in increasing order of number of
characters present in the array m_bData.
Is my understanding and assumption regarding the input params for
function "doeswhat" correct?Note that I dont have full code with me,so
this code  puzzled me,so I have to make it out myself!.

Sorry if it looks too immature to ask,but I thought better learn now
then never.I wish I am able to prove to my friend that I am
correct,though I am ready to accept my fault incase I am disproved with
proper proof.

I appologise incase this OT.Please refer me to proper group incase this
is OT.

Looking farward to all your replys and advanced thanks for the same,
Regards,
s.subbarayan


Re: efficient way of collating (mixing) two linked lists using C
Quoted text here. Click to load it

Answer deleted due to later discovery that the OP multi-posted the
same query on at least one other newsgroup.  This obnoxious
behaviour should not be rewarded.

--
"If you want to post a followup via groups.google.com, don't use
 the broken "Reply" link at the bottom of the article.  Click on
We've slightly trimmed the long signature. Click to see the full one.
Re: efficient way of collating (mixing) two linked lists using C
The self appointed usenet police.

Yes I top posted to annoy you.

Quoted text here. Click to load it




Re: efficient way of collating (mixing) two linked lists using C
Quoted text here. Click to load it

Good b....LONK.

--
"If you want to post a followup via groups.google.com, don't use
 the broken "Reply" link at the bottom of the article.  Click on
We've slightly trimmed the long signature. Click to see the full one.
Re: efficient way of collating (mixing) two linked lists using C
Did you have a bad day (or something?) and just do the usenet equivalent of
'going postal' on the OP?

<snip>

Quoted text here. Click to load it

<amusing signature quote snipped>

Quoted text here. Click to load it



Re: efficient way of collating (mixing) two linked lists using C

Quoted text here. Click to load it

The insistence on posting to one-and-only-one newsgroup is
a bit anal.  Unless the objection is to the multi-post, rather
than appropriately cross-posting.  But never attribute to
obnoxiousness what can be reasonable explained by ignorance.

The status can be upgraded to obnoxious upon discovery this
is not the OP's first offense...

Rufus



Re: efficient way of collating (mixing) two linked lists using C
What's obnoxious about it?

Quoted text here. Click to load it



Re: efficient way of collating (mixing) two linked lists using C
Quoted text here. Click to load it

This is an unmoderated group, as are the others on which I found
your posts.  Only you know where you actually posted, so only you
can set up a proper cross-posting with follow-ups set.

I am not feeling quite as mean today as I was then.  The objective,
as ever, is to educate the newbies on usenet so that they don't do
these foolish things.  I notice you still did not quote any
material to which you are replying, and have ignored the advice in
my sig. below.  This does not bode well for your ability to learn.

--
"If you want to post a followup via groups.google.com, don't use
 the broken "Reply" link at the bottom of the article.  Click on
We've slightly trimmed the long signature. Click to see the full one.
Re: efficient way of collating (mixing) two linked lists using C
Mr.CBF,
   Its good to know you are interested in educating the newby users of
usenet.But I believe there are better ways of educating from the
approach what you have taken.Looks like bashing to me or any one who
reads this.I feel better way is to put anything you want to say in
softer note then using harsh words like "foolishness" again in your
reply.I believe more then being a professional its good if we are
first of all good human beings.While you take interest in educating
others,it will be better if you put things in proper way so people get
it in right manner.You said I have not learnt to put reply,but it
seems you too should be able to learn using polite soft words.By the
way the problem why my  reply message appeared to you like that(not
following quote!) partly because of the problem with google.I still
get the old version of usenet in my webpage which did not show any
options what you have put in your quote!If only its updated I would be
happy enough to follow good things if put in proper way!

Regards,
s.subbarayan

Site Timeline