472,374 Members | 1,523 Online

# collating (mixing) two linked lists using C

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

Regards,
s.subbarayan

Nov 14 '05 #1
3 3164
s_**********@rediffmail.com wrote:

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

I just answered this in another newsgroup, and now I find you are
multi-posting. The proper way to do this is to cross-post AND to
set follow-ups to the single appropriate group at the same time.
Since the other answer is sitting in my unsent mail directory right
now, I shall go and purge it. We wouldn't want to encourage this
sort of usenet behaviour, would we? I shall also expect to see an
apology on all groups you posted this to (properly cross-posted
with follow-ups set), failing which it is the PLONK bin for you.

--
"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
"show options" at the top of the article, then click on the
Nov 14 '05 #2

"CBFalconer" <cb********@yahoo.com> wrote in message
news:42***************@yahoo.com...
s_**********@rediffmail.com wrote:

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

I just answered this in another newsgroup, and now I find you are
multi-posting. The proper way to do this is to cross-post AND to
set follow-ups to the single appropriate group at the same time.
Since the other answer is sitting in my unsent mail directory right
now, I shall go and purge it. We wouldn't want to encourage this
sort of usenet behaviour, would we? I shall also expect to see an
apology on all groups you posted this to (properly cross-posted
with follow-ups set), failing which it is the PLONK bin for you.

I'm following you around on this one CB! I replied to the other
prior to seeing this posting. This explanation is
reasonable and we probably would have forgiven you pasting it
into the other response as well!!

Rufus
Nov 14 '05 #3

<s_**********@rediffmail.com> wrote in message
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
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.

Regards,
s.subbarayan

PNODE defines a pointer to the _tagElement structure.
PNODE * ppnode; this is a definition of a pointer to a PNODE, that is a
pointer to, a pointer to a NODE structure.

You do not need so many levels of indirection.

Loks likes more of a sort than a shuffle/
Nov 14 '05 #4

This thread has been closed and replies have been disabled. Please start a new discussion.

### Similar topics

 2 by: Kakarot | last post by: I'm gona be very honest here, I suck at programming, *especially* at C++. It's funny because I actually like the idea of programming ... normally what I like I'm atleast decent at. But C++ is a... 7 by: Chris Ritchey | last post by: Hmmm I might scare people away from this one just by the title, or draw people in with a chalange :) I'm writting this program in c++, however I'm using char* instead of the string class, I am... 1 by: Booser | last post by: // Merge sort using circular linked list // By Jason Hall #include #include #include #include //#define debug 4 by: MJ | last post by: Hi I have written a prog for reversing a linked list I have used globle pointer Can any one tell me how I can modify this prog so that I dont have to use extra pointer Head1. When I reverse a LL... 12 by: joshd | last post by: Hello, Im sorry if this question has been asked before, but I did search before posting and couldnt find an answer to my problem. I have two classes each with corresponding linked lists, list1... 17 by: Ron Adam | last post by: I put together the following module today and would like some feedback on any obvious problems. Or even opinions of weather or not it is a good approach. While collating is not a difficult thing... 19 by: Dongsheng Ruan | last post by: with a cell class like this: #!/usr/bin/python import sys class Cell: def __init__( self, data, next=None ): self.data = data 51 by: Joerg Schoen | last post by: Hi folks! Everyone knows how to sort arrays (e. g. quicksort, heapsort etc.) For linked lists, mergesort is the typical choice. While I was looking for a optimized implementation of mergesort... 7 by: QiongZ | last post by: Hi, I just recently started studying C++ and basically copied an example in the textbook into VS2008, but it doesn't compile. I tried to modify the code by eliminating all the templates then it... 0 by: Naresh1 | last post by: What is WebLogic Admin Training? WebLogic Admin Training is a specialized program designed to equip individuals with the skills and knowledge required to effectively administer and manage Oracle... 0 by: WisdomUfot | last post by: It's an interesting question you've got about how Gmail hides the HTTP referrer when a link in an email is clicked. While I don't have the specific technical details, Gmail likely implements measures... 1 by: Matthew3360 | last post by: Hi, I have been trying to connect to a local host using php curl. But I am finding it hard to do this. I am doing the curl get request from my web server and have made sure to enable curl. I get a... 0 by: Oralloy | last post by: Hello Folks, I am trying to hook up a CPU which I designed using SystemC to I/O pins on an FPGA. My problem (spelled failure) is with the synthesis of my design into a bitstream, not the C++... 0 by: Carina712 | last post by: Setting background colors for Excel documents can help to improve the visual appeal of the document and make it easier to read and understand. Background colors can be used to highlight important... 0 by: Rahul1995seven | last post by: Introduction: In the realm of programming languages, Python has emerged as a powerhouse. With its simplicity, versatility, and robustness, Python has gained popularity among beginners and experts... 2 by: Ricardo de Mila | last post by: Dear people, good afternoon... I have a form in msAccess with lots of controls and a specific routine must be triggered if the mouse_down event happens in any control. Than I need to discover what... 1 by: ezappsrUS | last post by: Hi, I wonder if someone knows where I am going wrong below. I have a continuous form and two labels where only one would be visible depending on the checkbox being checked or not. Below is the... 0 by: jack2019x | last post by: hello, Is there code or static lib for hook swapchain present? I wanna hook dxgi swapchain present for dx11 and dx9.