Table of contents
1.
Introduction
1.1.
Problem Statement 
1.2.
Sample Example 
2.
Approach 1: Brute force approach 
2.1.
Steps of Algorithm 
2.2.
Pseudocode
2.3.
Implementation in C++
2.3.1.
Complexity analysis
3.
Approach 2: Optimized solution 
3.1.
Steps of Algorithm 
3.2.
Pseudocode
3.3.
Implementation in C++
3.4.
Implementation in Python 
3.4.1.
Complexity analysis
4.
Frequently Asked Questions
4.1.
Describe the applications of Linked Lists.
4.2.
What is the purpose of the dummy header in a linked list?
4.3.
What is the distinction between singly and doubly linked lists?
5.
Conclusion
Last Updated: Mar 27, 2024

Check whether the length of given Linked List is Even or Odd

Author Shivani Singh
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

In this problem, we need to check whether the length of our linked list is odd or even. There are various approaches to solve this problem. We will cover some of them here. So let us dig deeper into this problem statement as well as the solution. 

Recommended Topic, Floyds Algorithm

Problem Statement 

In this problem, we are given a linked list and should evaluate its length (count the number of nodes in the linked list) and whether it is Even or Odd.

The term 'even' indicates that the linked list has an even number of nodes.

The term 'odd' indicates that the number of nodes in the linked list is odd.

Let us understand this problem statement with the help of an example.

Sample Example 

Given is a linked list below. We have to count the total number of nodes and decide whether it is even or odd.

The following is the output of the above input: Even (since the count of the total number of nodes is 4 and 4 % 2 is equal to 0).

We simply have to count the total node in the list and determine whether it is odd or even. In the above test case, for example, the total number of nodes in the list is 4, and 4 is an even number, so the output is 'Even'. The output would have been 'Odd' if the number of nodes had been an odd number.

Source: linked list

Approach 1: Brute force approach 

This approach is very simple to implement and straightforward. In this approach, we simply count the total number of nodes in the linked list by iterating the given list and printing the output based on whether the count is odd or even. 

Let us see its algorithm. 

Steps of Algorithm 

Step 1: Create a temporary pointer and a variable named- length. Set the pointer to the very first node of the linked list and initialize length = 0.

Step 2: Begin iterating through the linked list, and with the traversal of every node, increase the value of length with each valid node.

Step 3: Variable length will give us the length of the linked list after iteration. We just need to calculate the length value. I.e. if (length  %  2 == 0), the linked list is of even length.

And if length  %  2 == 1), the linked list is of odd length. 

Let us understand this approach with the help of a diagram.

In this linked list, we will create a variable-length = 0. After traversing the whole linked list, we will get the value of length = 6. And after calculating its mod with 2. We will get to know that the linked list is of even length.  

Pseudocode

bool even_odd_length(struct node* link_list){
    int length=0;  // Counter to keep the track of the length of the linked list.
    
    while(link_list){  // Iterate the linked list.
        link_list=link_list->next;
         length=length+1; // increment the counter with every node visited.
    }
    if(length%2==0){ // Length even, return true
        return true;
    }else{
        return false;
    }
}
You can also try this code with Online C++ Compiler
Run Code

 

Let us see the implementation of this approach in the next section of this blog.

Implementation in C++

#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)
{
     int counter=0;  // Counter to keep the track of the length of the linked list.
    
    while(head){  // Iterate the linked list.
        head=head->next;
        counter=counter+1; // increment the counter with every node visited.
    }
    if(counter%2==0){ // Length even, return true
        return true;
    }else{
        return false;
    }
}


int main()
{
    Node* head = NULL;
    head = new Node(10);
    head->next = new Node(20);
    head->next->next = new Node(40);
    //head->next->next->next = new Node(60);
    
    if(is_length_even(head)){ // Check whether the linked list has even length or odd.
        cout<<"even length";
    }else{
        cout<<"odd length";
    }
    return 0;
}
You can also try this code with Online C++ Compiler
Run Code

 

Output:

odd length

 

Let us analyze the time and complexity of the above implementation.

Complexity analysis

Time complexity

As we have to traverse the linked list whole to know the length. So this approach will take O(N), where N is the total number of nodes in the linked list. 

Space complexity

In this approach, we only need a pointer variable and an integer variable: length. So this will not cost any memory space. And it will take O(1). 

Approach 2: Optimized solution 

In this approach, we will maintain a temporary pointer going to point to the head of the linked list and move it by cutting two nodes at a time.

When the pointer reaches the end of the linked list, one of two things can happen:

Either way, it will be NULL or it will point to the last node on our list.

Because we moved our pointer two nodes at a time if it is pointing to NULL, the length of the input is guaranteed to be even; otherwise, it is odd.

Steps of Algorithm 

Step 1: Create a temporary pointer variable for traversal and point it to the linked list's head.

Step 2: Traverse the list by shifting two nodes forward at a time.

Step 3: Iterate until the pointer variable reaches the end(NULL) or the last node in the linked list.

Step 4: At the end of this phase, if the pointer variable points to a node, the length is odd; otherwise, the length is even.

Let us understand this approach with the help of an example.

Source: linked list

Here in this example, we can see that firstly the head is pointing to the first node of the list. Then as it is iterating the list forward, the head node is pointing to the end of the list, and it is not null. That means this linked list is odd in length. 

Pseudocode

bool is_length_even(Node* head)
{
    while (head && head->next)
    {
        head = head->next->next;
    }
    if (head != NULL)
        return false;
    return true;
}
You can also try this code with Online C++ Compiler
Run Code

Implementation in C++

#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) // Iterate until their is no node left or it's the last node.
    {
        head = head->next->next;  // Jump 2 nodes at a time.
    }
/ After all the jumping and iteration, If the pointer is pointing to the last node and not the NULL, then it means it has an odd length
    if (head != NULL)
        return false;
    return true;
}


int main()
{
    Node* head = NULL;
    head = new Node(10);
    head->next = new Node(20);
    head->next->next = new Node(40);
    head->next->next->next = new Node(60);
    
    if(is_length_even(head)){  // Check whether the linked list has even length or odd.
        cout<<"even length";
    }else{
        cout<<"odd length";
    }
    return 0;
}
You can also try this code with Online C++ Compiler
Run Code

 

Output:

even length

 

Implementation in Python 

Implementation in Python
class LinkedList:
    def __init__(self, data, next = None):
        self.val = data
        self.next = next


def make_list(elements):
    head = LinkedList(elements[0])
    for element in elements[1:]:
        ptr = head
        while ptr.next:
            ptr = ptr.next
        ptr.next = LinkedList(element)
        
    return head
        
def solve(head): 
    while head != None and head.next != None:  
        head = head.next.next
              
    if head == None: 
        return "Linked List is of even length"
    return "Linked List is of odd length"

head = make_list([10,20,40,60])
print(solve(head))
You can also try this code with Online Python Compiler
Run Code

 

Output: 

Linked List is of even length

 

Now let us analyze the time and complexity of this approach.

Complexity analysis

Time complexity 

The time complexity of this algorithm is O(N). but as in this approach, we are skipping half the nodes, it will remain the same because here we are taking the larger value of N. and on a large scale O(N) and O(N/2) come in the same order. 

Space complexity

The space complexity is O(1) as no other extra data structures are used here.

Frequently Asked Questions

Describe the applications of Linked Lists.

Linked lists are used in implementing other data structures like queues, stacks, and graphs. You don't need to know the size of a linked list ahead of time.  You can add elements at the start and the end of a linked list.

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.

What is the distinction between singly and doubly linked lists?

Nodes in a doubly-linked list have three fields: an integer number and Two links to other nodes. One should point to the previous node, while the other should point to the next node.

A singly linked list, on the other hand, contains only points to the next node.

Conclusion

To conclude this blog, firstly we discussed the problem statement and different ways to solve the problems. For the first approach, we discussed its algorithm, pseudo-code, and complexities. And then we discussed another approach. We eventually saw how both the ways are different from each other. 

Refer to our guided paths on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must have a look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Live masterclass