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

Comments

  1. initializations:

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

    ReplyDelete

Post a Comment

Popular posts from this blog