Is Linked List Length Even?

Given a linked list, your task is to complete the function isLengthEven() which contains the head of the linked list, and check whether the length of the linked list is even or not. Return true if it is even, otherwise false.

Examples:

Input: Linked list: 12->52->10->47->95->0

Output: true
Explanation: The length of the linked list is 6 which is even, hence returned true.

Input: Linked list: 9->4->3

Output: false
Explanation: The length of the linked list is 3 which is odd, hence returned false.

Expected Time Complexity: O(n)
Expected Auxillary Space: O(1)

Constraints:
1 <= number of nodes <= 10⁵
1 <= elements of the linked list <= 10⁵

Approach 01:

class Solution {
  public:
    bool isLengthEven(struct Node **head) {
        Node* data = *head;
        int length = 0;
        while(data){
            ++length;
            data = data->next;
        }
        return (length%2 == 0);
    }
};

class Solution:
    # your task is to complete this function
    # function should return false if length is even
    # else return true
    def isLengthEven(self, head):
        length = 0
        while(head is not None):
            length += 1
            head = head.next
        return (length%2 == 0)

Time Complexity

• Traversal of Linked List:

  The function traverses the entire linked list once to determine its length, which takes \( O(N) \), where \( N \) is the number of nodes in the list.

• Overall Time Complexity:

  The overall time complexity is \( O(N) \).

Space Complexity

• Variable Storage:

  Only a constant amount of space is required to store the data pointer and length variable. This means the space complexity is \( O(1) \).