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

Last Updated on November 10, 2022 by Prepbytes

This article helps you to tackle the linked list’s 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’s understand the problem statement more clearly.

Problem Statement of even odd linked list

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 of even odd linked list

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 of even odd linked list

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 of even odd linked list – O(n) [ where n is the number of nodes present in the list].

Space Complexity of even odd linked list – 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 of even odd linked list

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 of even odd linked list – 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 of even odd linked list – O(1)

Dry run of even odd linked list

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 of even odd linked list

#include<stdio.h>
#include<stdlib.h>
 
struct Node
{
    int data;
    struct Node* next;
};
 
// Function to check the length of linklist
int LinkedListLength(struct Node* head)
{
    while (head && head->next)
    {
        head = head->next->next;
    }
    if (!head)
        return 0;
    return 1;
}
void push(struct Node** head, int info)
{
    struct Node* node = (struct Node*) malloc(sizeof(struct Node));
     
    node->data = info;
    node->next = (*head);
 
    (*head) = node;
}

int main(void)
{
    struct Node* head = NULL;
    push(&head, 4);
    push(&head, 5);
    push(&head, 7);
    push(&head, 2);
    push(&head, 9);
    push(&head, 6);
    push(&head, 1);
    push(&head, 2);
    push(&head, 0);
    push(&head, 5);
    push(&head, 5);
    int check = LinkedListLength(head);
    if(check == 0)
    {
        printf("Even\n");
    }
    else
    {
        printf("Odd\n");
    }
    return 0;
}

#include<bits stdc++.h="">
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;
}

class Node 
{
    int data;
    Node next;
    Node()
    {
        
    }
    Node(int data)
    {
        this.data=data;
    }
    boolean is_length_even(Node head)
    {
        while(head!=null && head.next!=null)
        {
            head=head.next.next;
        }
        if(head!=null)
        {
            return false;
        }
        return true;
    }
}

public class EvenOdd 
{
    public static void main(String[] args) 
    {
        Node check=new Node();
        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(check.is_length_even(head))
        {
            System.out.println("Even");
        }
        else 
        {
            System.out.println("Odd");
        }
    }    
}

class Node:
	def __init__(self, data):
		self.data = data
		self.next = None
		self.head = None

	def is_length_even(self):
		while (self.head and self.head.next):
			self.head = self.head.next.next
			
		if(self.head != None):
			return False
		return True

head = Node(7)
head.next = Node(2)
head.next.next = Node(4)
head.next.next.next = Node(23)
head.next.next.next.next = Node(31)

check = head.is_length_even()

if(check == 0) :
	print("Even")
else:
	print("Odd")

Output

Odd

Conclusion

To conclude this blog, we discussed the problem statement, and different ways to solve the problems. We have discussed two approaches with efficient dry run. We hope this article will helps you to clear your doubts.
If you want to practice more questions on linked lists, feel free to solve them at Linked List.

FAQs related to even odd linked list

1. Describe the applications of linked lists?


Linked list are used for implementing data structures like stack, queue, graph and many more.


2. What is the purpose of the dummy header in a linked list?


The dummy header in a linked list includes the first record of the actual data.


3. What is the length of the linked list?


The length of the linked list is the total number of nodes in the linked list.