339. Check if Linked List has Even or Odd Length

Given the head of a singly linked list, determine if the list has an even or odd number of nodes.

Return "Even" if the count is even, "Odd" if odd.

Use the fast pointer trick: move one pointer 2 steps at a time. If it reaches NULL exactly, length is even; if it ends on a node, length is odd.

Input: Head of a singly linked list.

Output: "Even" or "Odd".

Examples

Example 1

Input: [1,2,3,4]
Output: Even
Explanation: 4 nodes. Even.

Example 2

Input: [1,2,3]
Output: Odd
Explanation: 3 nodes. Odd.

Example 3

Input: [7]
Output: Odd
Explanation: 1 node. Odd.