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;
}