Consider a singly-linked list of nodes, where each node contains an integer and a pointer.

a)Write an ITERATIVE function that returns TRUE (1) if the list has an EVEN number of nodes; otherwise return FALSE (0). Code in the language of your choice and include the declaration of your data structure. The prototype in C is:

int even(node_ptr p)

b) [10 points] Repeat using RECURSION.

c) State which solution is better and give a brief justification.

Special Note: Using a counter is not allowed (NO CREDIT will be assigned).

I cannot think of any way to do this without using a counter.....any help will be appreciated

2. Originally Posted by lastrial
I cannot think of any way to do this without using a counter.....any help will be appreciated
Hint: Boolean toggle.

3. hmmmmm....

This what I have come up with.....donno where I goofed up

Code:
```int counters (LIST L){
int flag = 0;
position p;
if (p){
flag = 0;
p = p->next;
if (p){
flag = 1;
p = p->next;
}
return flag = 0; // if 2

}//end if 1

return flag;
}```

4. You would need a while loop instead of that if block.

Here's some pseudo-code :

Code:
```int counters(LIST l){
flag = 0; //  0 == even, 1== odd
if(l != null)
flag = 1;  //  Has at least one element

while(l has next)
{
l = l.next
flag++;
flag = flag &#37; 2;
}

return flag
}```

5. If you want extra marks, check if the result is odd or even with bitwise ops (cause its faster than mod')
http://en.allexperts.com/q/C-1040/Bit-Operators.htm

6. I am not supposed to use a counter and code shown above uses it.

7. No it does not, flag is always either 0 or 1.

8. Oh so...using flag++ doesn't fall under using a counter huh.....thanks for clearing that up. Thanks very much happy reaper.

9. He's modifying the flag after he increments it so it'll always be 0 or 1. That's what a boolean flag is.

Technically, you could just do flag = !flag if you just wanted to set flag from true to false or false to true.

10. Thanks verymuch guys I followed both the solutions......using mod and triggering....

11. What the heck are people using mod for?

Iterative:

Code:
```int even_or_odd(nodeptr p)
{
int is_even = 1;
while(p)
{
is_even = !is_even;
p = p->next;
}
return is_even;
}```
Recursive:

Code:
```/* Must be called with is_even == 1 */
int even_or_odd(nodeptr p, int is_even)
{
if(!p) return is_even;
return even_or_odd(p->next, !is_even);
}```

12. /* Must be called with is_even == 1 */
Are you sure?

13. Are you sure?
Perhaps more accurately: must be called with is_even != 0

14. Originally Posted by MacGyver
Are you sure?
I really meant what Laserlight said. Any non-zero value is fine. For that matter, calling it with zero would also be fine, but the sense of the return code would be reversed (i.e. it would check for oddness instead of evenness, thus the name of the function "even_or_odd")

EDIT: Furthermore, you could look at the comment as an interface specification instead of a reflection of the implementation. Maybe the implementation of even_or_odd() changes in the future so that it really DOES require 1 (and only 1). But I decided to assert this restriction early on

15. I must be blind today. You're correct.