Re: Linked list problem (puzzle)




CBFalconer wrote:
Priya wrote:

Given a singly linked list, such that the contents of the nodes are
either TRUE(0xff) or FALSE(0x00), write a function that will split the
given list into two lists such that the number of nodes with content as
TRUE is the same in both the lists.
# Conditions:
1. You are given a pointer to the head of the list and the total number
of TRUE nodes in the list
2. You are not allowed to examine/determine/compare the content of a
node before trying to copy it to the new list. The only read operation
on the content field permitted is while copying the node.

It is fairly hard to attain your objective when the original number
of TRUE nodes is odd. Assuming that is not so, simply distribute
the TRUE nodes alternately to each output list. There seems to be
no restriction as to the final distribution of FALSE nodes, but if
there was you could follow a similar strategy for them.

I think you are missing the point here that you are not allowed to look
at the node until you start copying it. For instance, suppose the list
is four nodes long - two TRUE nodes and two FALSE nodes. We put the
first node in list 1, noting as we do so that it is a TRUE node. We
therefore have to put the second node into list 2, in case it's the
other TRUE. Copying it there, we find that it was a FALSE. We have to
put the third node into list 2, again in case it turns out to the the
other TRUE; but it too turns out to be a FALSE. So we can't split the
FALSEs evenly between the two lists. But by changing list every time we
find we have copied a TRUE, we can balance out the TRUEs between the
two lists.

Paul.

.