Segregate Even and Odd nodes in a Linked List
Segregate even and odd nodes in a Linked List
In this problem, we have given a linked list with integer numbers. We need to modify the given linked list in such a way that all even numbers appear before all the odd numbers in the new linked list. We will also preserve the order of even and odd numbers.
Examples:
Input: 19 -> 13 -> 6 -> 10 -> 2 -> 7 -> 12 -> 1 -> 8 ->NULL
Output: 6 -> 10 -> 2 -> 12 -> 8 -> 19 -> 13 -> 7 -> 1 -> NULL
Note: If all numbers are even then do not change the list
Input: 2 -> 4 -> 6 ->NULL
Output: 2 -> 4 -> 6 -> NULL
Note:If all numbers are odd, then do not change the list
Input: 1 ->3 ->5 ->7 ->NULL
Output: 1 ->3 ->5 ->7 ->NULL
Method 1:
1) Firstly, we will move the pointer to the last node.
2) Then, we will move all the odd nodes to the end.
a) We will consider all odd nodes before the first even node and move them to the end.
b)Next, we will Change the head pointer to point to the first even node.
c) Then, we will consider all odd nodes after the first even node and move them to the end.
C program to segregate even and odd nodes in a Linked List by method 1
#include<stdio.h>
#include<stdlib.h>
//The structure of the node
struct node
{
int info;
struct node * next;
};
struct node * start = NULL;
// For inserting the elements in the linked list
void add(int item)
{
struct node * t, * p;
t = (struct node * )malloc( sizeof( struct node ));
if(start == NULL)
{
start = t;
start -> info = item;
start -> next = NULL;
return;
}
else
{
struct node * p = start;
while(p -> next != NULL)
{
p = p -> next;
}
p -> next = t;
p = p -> next;
p -> info = item;
p -> next = NULL;
}
}
// program to segregate even and odd nodes in a Linked List
voidsegregateEvenOdd(struct node **head_ref)
{
struct node *end = *head_ref;
struct node *prev = NULL;
struct node *curr = *head_ref;
while (end->next != NULL)
end = end->next;
struct node *new_end = end;
while (curr->info %2 != 0 &&curr != end)
{
new_end->next = curr;
curr = curr->next;
new_end->next->next = NULL;
new_end = new_end->next;
}
if (curr->info%2 == 0)
{
*head_ref = curr;
while (curr != end)
{
if ( (curr->info)%2 == 0 )
{
prev = curr;
curr = curr->next;
}
else
{
prev->next = curr->next;
curr->next = NULL;
new_end->next = curr;
new_end = curr;
curr = prev->next;
}
}
}
elseprev = curr;
if (new_end!=end && (end->info)%2 != 0)
{
prev->next = end->next;
end->next = NULL;
new_end->next = end;
}
return;
}
// To display the elements of the linked list
void traverse(struct node * t)
{
if(t == NULL)
{
printf(" Linked list is empty\n");
}
while(t -> next != NULL)
{
printf("%d -> ", t -> info);
t = t -> next;
}
printf("%d\n", t -> info);
}
// Driver Function
int main()
{
add(19);
add(13);
add(6);
add(10);
add(2);
add(7);
add(12);
add(1);
add(8);
printf("Linked List before:\n");
traverse(start);
segregateEvenOdd(&start);
printf("Linked List after:\n");
traverse(start);
return 0;
}
Output:
Method 2:
This method will split the given linked list into two parts, one part containing all the even nodes and the other part containing all the odd nodes. Finally, we will link the odd node linked list after the even node linked list.
C program to segregate even and odd nodes in a Linked List by method 2
#include<stdio.h>
#include<stdlib.h>
// The structure of the node
struct node
{
int info;
struct node * next;
};
struct node * start = NULL;
// For inserting the elements in the linked list
void add(int item)
{
struct node * t, * p;
t = (struct node * )malloc( sizeof( struct node ));
if(start == NULL)
{
start = t;
start -> info = item;
start -> next = NULL;
return;
}
else
{
struct node * p = start;
while(p -> next != NULL)
{
p = p -> next;
}
p -> next = t;
p = p -> next;
p -> info = item;
p -> next = NULL;
}
}
// program to segregate even and odd nodes in a Linked List
voidsegregateEvenOdd(struct node **head_ref)
{
struct node *evenStart = NULL;
struct node *evenEnd = NULL;
struct node *oddStart = NULL;
struct node *oddEnd = NULL;
struct node *currNode = *head_ref;
while(currNode != NULL){
intval = currNode -> info;
if(val % 2 == 0) {
if(evenStart == NULL){
evenStart = currNode;
evenEnd = evenStart;
}
else{
evenEnd -> next = currNode;
evenEnd = evenEnd -> next;
}
}
else{
if(oddStart == NULL){
oddStart = currNode;
oddEnd = oddStart;
}
else{
oddEnd -> next = currNode;
oddEnd = oddEnd -> next;
}
}
currNode = currNode -> next;
}
if(oddStart == NULL || evenStart == NULL){
return;
}
evenEnd -> next = oddStart;
oddEnd -> next = NULL;
*head_ref = evenStart;
}
// To display the elements of the linked list
void traverse(struct node * t)
{
if(t == NULL)
{
printf(" Linked list is empty\n");
}
while(t -> next != NULL)
{
printf("%d -> ", t -> info);
t = t -> next;
}
printf("%d\n", t -> info);
}
// Driver Function
int main()
{
add(3);
add(5);
add(9);
add(11);
add(13);
add(15);
add(17);
printf("Linked List before:\n");
traverse(start);
segregateEvenOdd(&start);
printf("Linked List after:\n");
traverse(start);
return 0;
}
Output:
