Check whether the Linked List has an even length or odd?

Question: Given a Linked List, we need to find out if the number of nodes in the Link List are odd or even?

Input: 4, 8, 15, 16, 23, 42

Output: EVEN

The most easy method to solve this problem would be by traversing the entire Linked List and counting the number of nodes as we go. As the loop is finished, we can check if the count is even or odd.

A Simpler Way:

Another way of solving this problem in less time would be advancing 2 nodes at a time. When the iteration is complete:

• If we are at a NULL position, that means that the length was EVEN.
• If we are at a node that has a certain value, then the length of the list is ODD.

Here is an implementation of this approach:-

#include

struct node
{
	int data;
	struct node * next;
};

// defining a function, that returns 1, if the list is EVEN
int isLengthEven(struct node * listHead)
{
	// we need to traverse the List, until we reach the end
	// checking both conditions, NULL and the last Node
	while(listHead !=NULL && listHead -> next != NULL)
	{
		//advance 2 nodes at a time
		listHead = listHead -> next -> next;
	}

	// if we are at a NULL, means EVEN, return 1
	if(listHead == NULL)
		return 1;
	else
		return 0;
}

struct node * addElement(struct node *head, int number)
{
	struct node * temp = (struct node*)malloc(sizeof(struct node));
	temp -> data = number;
	temp -> next = NULL;
	struct node * temp2 = head;
	while(temp2 -> next != NULL)
		temp2 = temp2 -> next;
	temp2 -> next = temp;
	return head;
}

int main(void)
{
	//creating a list
	struct node * listHead = (struct node*)malloc(sizeof(struct node));
	listHead->data = 4;
	listHead->next = NULL;
	listHead = addElement(listHead, 8);
	listHead = addElement(listHead, 15);
	listHead = addElement(listHead, 16);
	listHead = addElement(listHead, 23);
	listHead = addElement(listHead, 42);

	if(isLengthEven(listHead))
		printf("EVEN\n");
	else
		printf("ODD\n");

	return 0;
}