# Determining if the length of LinkedList is even or odd

Today, I tackled this coding question: Given a singly-linked list, check whether its length is even or odd in a single pass. An Empty list has 0 nodes which makes the number of nodes in it even.

Would the time complexity of my code be O(n)? Do you guys see any improvements that can be made?

public Boolean isListEven(ListNode head) {

return true;
}

return false;
}

int count = 1;
count = count + 2;
}

count = count + 1;
}

return (count % 2 == 0);
}

• You can store the size of your list in an int. Everytime you insert an element or removing one you increese or decreese the size. If you then call this method, you have the value instantly. – Shinigami Mar 21 '17 at 5:04

The method signature is a bit odd, returning a Boolean object instead of a primitive boolean. A clearer name would be isListLengthEven(). The function could be static, since it does not rely on any object state.

If the list has one node, then your code will crash on if(head.next.next == null). In general, you should avoid cluttering your code with unnecessary special cases.

You don't need to keep track of count. This solution, like yours, is O(n), but it is much simpler:

public static boolean isListLengthEven(ListNode head) {

The trick is to observe the loop invariant: each iteration through the loop, it advances head by two nodes, so that the picture at the top of the loop is always equivalent to the original. If it can't advance by two, then the list has an odd length.
• @TheLearner I've added an explanation. A for loop has an initialization, test, and update field; the semicolon just indicates that nothing needs to be done for the initialization. – 200_success Mar 21 '17 at 16:42