Check whether the length of given linked list is Even or Odd

Problem Statement

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.

  • 'Even' means that the linked list contain even number of nodes (count%2==0).
  • 'Odd' means that the count of the number of nodes in linked list is odd (count%2==1).

Problem Statement Understanding

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.

Let the input be the list given below:

Output of above input will be:- Odd (since count of the total number of nodes are 5 and 5%2 is equal to 1).

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'.

Approach 1

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.

Time Complexity - O(n) [ where n is the number of nodes present in the list].

Space Complexity - O(1).

The above approach is pretty trivial but we need to travel the whole list to say whether the count is odd or even.

Can we do better than this?
Well, we can optimise it a bit more.

Helpful Observations

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.

Approach 2

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.

When the pointer comes to the end of the linked list, there are two possibilities:

  • Either it will point to NULL.
  • Or it will point to the last node of our list.

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.

Time complexity - 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.

Space Complexity - O(1)

Dry run

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'.

Code Implementation




#include
Using namespace std;
class Node
{
    public:
    int data;
    Node* next;
    Node(int x){
        data = x;
   next = NULL;
    }
};
 
bool is_length_even(Node* head)
{
    while (head && head->next)
    {
        head = head->next->next;
    }
    if (head != NULL)
        return false;
    return true;
}

int main(void)
{
    Node* head = NULL;
    head = new Node(7);
    head->next = new Node(2);
    head->next->next = new Node(4);
    head->next->next->next = new Node(23);
    head->->next->next->next->next = new Node(31);
    
    if(is_length_even(head)){
        cout<<”Even”;
    }else{
        cout<<”Odd”;
    }
    return 0;
}

Output

Odd

So, in this blog, we have tried to explain how you can find whether the length of a given linked list is odd or even in the most optimal way. If you want to practice more questions on linked lists, feel free to solve them at Linked List.

Previous post Segregate even and odd nodes in a Linked List
Next post Function to delete a Linked list

Leave a Reply

Your email address will not be published. Required fields are marked *