Given a Linked List of integers, write a function to modify the linked list such that all even numbers appear before all the odd numbers in the modified linked list. Also, keep the order of even and odd numbers same.
Method 2
The idea is to split the linked list into two: one containing all even nodes and other containing all odd nodes. And finally attach the odd node linked list after the even node linked list.
To split the Linked List, traverse the original Linked List and move all odd nodes to a separate Linked List of all odd nodes. At the end of loop, the original list will have all the even nodes and the odd node list will have all the odd nodes. To keep the ordering of all nodes same, we must insert all the odd nodes at the end of the odd node list. And to do that in constant time, we must keep track of last pointer in the odd node list.
Method 1
Read full article from Segregate even and odd nodes in a Linked List | GeeksforGeeks
Method 2
The idea is to split the linked list into two: one containing all even nodes and other containing all odd nodes. And finally attach the odd node linked list after the even node linked list.
To split the Linked List, traverse the original Linked List and move all odd nodes to a separate Linked List of all odd nodes. At the end of loop, the original list will have all the even nodes and the odd node list will have all the odd nodes. To keep the ordering of all nodes same, we must insert all the odd nodes at the end of the odd node list. And to do that in constant time, we must keep track of last pointer in the odd node list.
Method 1
The idea is to get pointer to the last node of list. And then traverse the list starting from the head node and move the odd valued nodes from their current position to end of the list.
…1) Get pointer to the last node.
…2) Move all the odd nodes to the end.
……..a) Consider all odd nodes before the first even node and move them to end.
……..b) Change the head pointer to point to the first even node.
……..b) Consider all odd nodes after the first even node and move them to the end.
……..a) Consider all odd nodes before the first even node and move them to end.
……..b) Change the head pointer to point to the first even node.
……..b) Consider all odd nodes after the first even node and move them to the end.
void segregateEvenOdd(struct node **head_ref){ struct node *end = *head_ref; struct node *prev = NULL; struct node *curr = *head_ref; /* Get pointer to the last node */ while (end->next != NULL) end = end->next; struct node *new_end = end; /* Consider all odd nodes before the first even node and move then after end */ while (curr->data %2 != 0 && curr != end) { new_end->next = curr; curr = curr->next; new_end->next->next = NULL; new_end = new_end->next; } // 10->8->17->17->15 /* Do following steps only if there is any even node */ if (curr->data%2 == 0) { /* Change the head pointer to point to first even node */ *head_ref = curr; /* now current points to the first even node */ while (curr != end) { if ( (curr->data)%2 == 0 ) { prev = curr; curr = curr->next; } else { /* break the link between prev and current */ prev->next = curr->next; /* Make next of curr as NULL */ curr->next = NULL; /* Move curr to end */ new_end->next = curr; /* make curr as new end of list */ new_end = curr; /* Update current pointer to next of the moved node */ curr = prev->next; } } } /* We must have prev set before executing lines following this statement */ else prev = curr; /* If there are more than 1 odd nodes and end of original list is odd then move this node to end to maintain same order of odd numbers in modified list */ if (new_end!=end && (end->data)%2 != 0) { prev->next = end->next; end->next = NULL; new_end->next = end; } return;}