Modify linked list into even and odd elements
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.
Examples:
Input: 17->15->8->12->10->5->4->1->7->6->NULL
Output: 8->12->10->4->6->17->15->5->1->7->NULL
Input: 17->15->8->12->10->5->4->1->7->6->NULL
Output: 8->12->10->4->6->17->15->5->1->7->NULL
initializations:
ReplyDeleteevenHead = null; // will be assigned atmost once
evenTail = null; // keeps on changing
oddHead = null; // will be assigned atmost once
oddTail = null; // keeps on changing
curr = root;
loop:
while (curr != null)
{
if(curr->data == even)
{
if(evenHead == null) evenHead = curr;
evenTail = curr;
next = curr->next;
if(next == null) break;
// even -> odd
if(next->data == odd)
{
if(oddTail != null)
{
oddTail->next = next;
oddTail = next;
}
else
{
oddHead = next;
oddTail = next;
}
}
// even -> even
else if(next->data == even)
{
evenTail = next;
}
curr = next->next;
}
else if(curr->data == odd)
{
if(oddHead == null) oddHead = curr;
oddTail == curr;
next = curr->next;
if(next == null) break;
// odd -> even
if(next->data == even)
{
if(evenTail != null)
{
evenTail->next = next;
evenTail = next;
}
else
{
evenHead = next;
evenTail = next;
}
}
// odd -> odd
else if(next->data == odd)
{
oddTail = next;
}
curr = next->next;
}
}
if(evenHead != null)
{
root = evenHead;
evenTail = oddHead;
}
else
{
root = oddHead;
}