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.
Looking farward to all your replys and advanced thanks for the same,
Regards,
s.subbarayan
