![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645185859766-linked%20list%20even%20or%20odd.png\")
<\/p>\n<\/p>\n
This article helps you to tackle the linked list\u2019s challenge i.e. Check whether the length of a given linked list is Even or Odd also this problem is known as an even odd linked list. Let\u2019s understand the problem statement more clearly.<\/p>\n
In this problem we are given a linked list and we have to find the length of the linked list i.e. count the number of nodes in the linked list, and tell whether the linked list is Even or Odd.<\/p>\n
We will be given a linked list as input and we need to count the total nodes in it and say whether the count is even or odd.<\/p>\n
Let the input be the list given below:<\/p>\n
![\"\"](\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/08\/Untitled-9-01.png\")
<\/p>\n
Output of above input will be:- Odd (since count of the total number of nodes are 5 and 5%2 is equal to 1).<\/p>\n
We just need to count the total number of nodes in the list and say whether the count is odd or even. For example, in the above test case, the total number of nodes in the list are 5 and 5 is an odd number so the output will be ‘Odd’. Had the count of nodes been an even number, the output would have been ‘Even’.<\/p>\n
In this approach, we simply count the total number of nodes present in the linked list by iterating the given list and depending on whether the count comes odd or even, we print the output.<\/p>\n
Time Complexity of even odd linked list <\/strong> – O(n) [ where n is the number of nodes present in the list].<\/p>\n Space Complexity of even odd linked list <\/strong> – O(1).<\/p>\n The above approach is pretty trivial but we need to travel the whole list to say whether the count is odd or even. <\/p>\n Can we do better than this? If we keep a pointer that will move two nodes at a time then it is obvious that when we will reach the end of the list if the length is odd, it would be pointing to the last node of the list and if the length is even, it would be pointing to a NULL pointer because it would skip the last node since it is advancing by skipping the nodes in pairs.<\/p>\n In this approach, we keep a temporary pointer pointing to the head of the linked list and move it by skipping two nodes at a time.<\/p>\n When the pointer comes to the end of the linked list, there are two possibilities:<\/p>\n Since we moved our pointer skipping 2 nodes at a time if it is pointing to NULL, it is guaranteed that the length of the input is even, otherwise, it is odd.<\/p>\n Time complexity of even odd linked list <\/strong> – O(n), asymptotically, time complexity will remain linear but in this approach, we are travelling only half the total number of nodes i.e. n\/2.<\/p>\n Space Complexity of even odd linked list <\/strong> – O(1)<\/p>\n Since our head is pointing to the last node of our list, the length of the list is odd. So our output will be ‘Odd’. <\/p>\n
\nWell, we can optimise it a bit more. <\/p>\nHelpful Observations<\/h3>\n
Approach 2 of even odd linked list <\/h3>\n
\n
Dry run of even odd linked list <\/h3>\n
![\"\"](\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/08\/Untitled-10-01.png\")
<\/p>\nCode Implementation of even odd linked list <\/h3>\n\t\t\t\t\t\t