Segregate Odd-Even
There is a wedding ceremony at NinjaLand. The bride and groom want everybody to play a game and thus, they have blindfolded the attendees. The people from the bride’s side are holding odd numbers and people from the groom’s side are holding the even numbers. For the game to start quickly, all the bride’s side people should come first, followed by the groom’s side people in the same order.

The attendees of the wedding with their numbers are given in the form of a Singly Linked List, arranged randomly.

A singly linked list is a type of linked list that is unidirectional; that is, it can be traversed in only one direction from head to the last node (tail).

Example:

The attendees holding numbers from 1, 4, 3 are shown:

As the organizers are busy, you have to arrange all the people by arranging the bride’s side people first followed by the groom’s side people sequentially.

Note:

For the above example 1 - 4 - 3, 1 - 3 - 4 is the only correct answer, i.e nodes should be grouped sequentially. Hence, 3 - 1 - 4 is the wrong answer as we have to preserve the same order.

Input Format

The first line of input contains an integer T, the number of test cases. Then each test case follows. The first and the only line of every test case contains the elements of the singly linked list separated by a single space and terminated by -1. Hence, -1 would never be a list element.

Output Format:

For every test case, print the bride’s side attendees followed by the groom’s side attendees. The attendees/elements should be single-space separated, terminated by -1. The output of each test case is printed in a separate line.

Note :

You don't need to print the output, it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Segregate Odd-Even

There is a wedding ceremony at NinjaLand. The bride and groom want everybody to play a game and thus, they have blindfolded the attendees. The people from the bride’s side are holding odd numbers and people from the groom’s side are holding the even numbers. For the game to start quickly, all the bride’s side people should come first, followed by the groom’s side people in the same order.

The attendees of the wedding with their numbers are given in the form of a Singly Linked List, arranged randomly.

A singly linked list is a type of linked list that is unidirectional; that is, it can be traversed in only one direction from head to the last node (tail).

Example:

The attendees holding numbers from 1, 4, 3 are shown:

As the organizers are busy, you have to arrange all the people by arranging the bride’s side people first followed by the groom’s side people sequentially.

Note:

For the above example 1 -> 4 -> 3, 1 -> 3 -> 4 is the only correct answer, i.e nodes should be grouped sequentially. Hence, 3 -> 1 -> 4 is the wrong answer as we have to preserve the same order.

Input Format

The first line of input contains an integer T, the number of test cases. Then each test case follows.

The first and the only line of every test case contains the elements of the singly linked list separated by a single space and terminated by -1.
Hence, -1 would never be a list element.

Output Format:

For every test case, print the bride’s side attendees followed by the groom’s side attendees.
The attendees/elements should be single-space separated, terminated by -1.

The output of each test case is printed in a separate line.

Note :

You don't need to print the output, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N <= 5 * 10^4
0 <= data <= 10^4 and data != -1

Where 'N' denotes the number of elements in the Singly Linked List and 'data' represents the value of those elements.

Time Limit: 1 sec

Accepted Answer

Iterative Approach 1

As we have to arrange the nodes such that all the odd nodes should come before all the even nodes, we can move all the even valued nodes from their current positions to the end of the linked list.

Algorithm:

Initialise a pointer ‘LAST_NODE’ by NULL.
Traverse the linked list to the end and get the last node of the list which will be pointed by ‘LAST_NODE’.
Initialize a pointer ‘NEW_END’ by ‘LAST_NODE’.
Traverse the list and consider all the even valued nodes before the first odd valued node. Move them to the end of the list by connecting them after the ‘NEW_END’. Keep moving the ‘NEW_END’ forward.
If the list is completely traversed, return the head of the linked list as the list only contains even valued nodes.
Else, we encounter the first odd valued node, update the head pointer to point to this first odd node.
- Traverse the linked list from this node to the ‘LAST_NODE’, if any even valued node is encountered, move it to the end of the list by connecting them after the ‘NEW_END’. Keep moving the ‘NEW_END’ forward.
After the above process, all the even nodes will come after all the odd nodes.
Return the head of the modified linked list.

Space Complexity: O(1)Explanation:

O(1).

We are not using any extra data structure. Only constant additional space is required.

Time Complexity: O(n)Explanation:

O(N), where N is the number of nodes in the linked list.

Every node of the linked list is traversed only twice and thus, the final time complexity is O(2 * N) = O(N).

Python (3.5)

'''

    Time Complexity: O(N) 

    Space Complexity: O(1)

    

    Where N is the number of the nodes in the linked list.

'''



def segregateOddEven(head):

    lastNode = head



    # Loop to get the last node of the list.

    while (lastNode.next != None):

        lastNode = lastNode.next



    curr = head

    newHead, prev = None, None

    newEnd = lastNode



    '''

        Consider all even nodes before the first 

	    odd node and move them to the end.

    '''

    while (curr.data % 2 == 0 and curr != lastNode):



        prev = curr

        curr = curr.next



    # If curr is an even node, then the list contains all even nodes.

    if (curr.data % 2 == 0):

        return head



    # There are even valued nodes in the beginning of the list.

    if (curr != head):

        lastNode.next = head

        newEnd = prev

        prev.next = None

        newHead = curr



    # Update new head of the linked list.

    newHead = curr



    while (curr != lastNode):

        if (curr.data % 2 == 1):

            prev = curr

            curr = curr.next



        # Move the even valued node to the end of the list.

        else:

            prev.next = curr.next

            curr.next = None

            newEnd.next = curr

            newEnd = curr

            curr = prev.next



    # For handling the last node of the original linked list.

    if (newEnd != None and lastNode.data % 2 == 0):

        prev.next = lastNode.next

        lastNode.next = None

        newEnd.next = lastNode



    # Return modified head.

    return newHead

Java (SE 1.8)

/*

    Time Complexity: O(N) 

    Space Complexity: O(1)

    

    Where N is the number of the nodes in the linked list.

*/



public class Solution {



    public static Node segregateOddEven(Node head) {

        Node lastNode = head;



        // Loop to get the last node of the list.

        while (lastNode.next != null) {

            lastNode = lastNode.next;

        }



        Node curr = head;

        Node newHead = null, prev = null, newEnd = lastNode;



        /*

            Consider all even nodes before the first

            odd node and move them to the end.

         */

        while (curr.data % 2 == 0 && curr != lastNode) {

            prev = curr;

            curr = curr.next;

        }



        // If curr is an even node, then the list contains all even nodes.

        if (curr.data % 2 == 0) {

            return head;

        }



        // There are even valued nodes in the beginning of the list.

        if (curr != head) {

            lastNode.next = head;

            newEnd = prev;

            prev.next = null;

            newHead = curr;

        }



        // Update new head of the linked list.

        newHead = curr;



        while (curr != lastNode) {

            if (curr.data % 2 == 1) {

                prev = curr;

                curr = curr.next;

            }



            // Move the even valued node to the end of the list.

            else {

                prev.next = curr.next;

                curr.next = null;

                newEnd.next = curr;

                newEnd = curr;

                curr = prev.next;

            }

        }



        // For handling the last node of the original linked list.

        if (newEnd != null && lastNode.data % 2 == 0) {

            prev.next = lastNode.next;

            lastNode.next = null;

            newEnd.next = lastNode;

        }



        // Return modified head.

        return newHead;

    }

}

C++ (g++ 5.4)

/*

    Time Complexity: O(N) 

    Space Complexity: O(1)

    

    Where N is the number of the nodes in the linked list

*/



Node *segregateOddEven(Node *head)

{

    Node *lastNode = head;



    // Loop to get the last node of the list.

    while (lastNode->next != NULL)

    {

        lastNode = lastNode->next;

    }



    Node *curr = head;

    Node *newHead = NULL, *prev = NULL, *newEnd = lastNode;



    /*

		Consider all even nodes before the first 

		odd node and move them to the end. 

	*/

    while (curr->data % 2 == 0 && curr != lastNode)

    {

        prev = curr;

        curr = curr->next;

    }



    // If curr is an even node, then the list contains all even nodes.

    if (curr->data % 2 == 0)

    {

        return head;

    }



    // There are even valued nodes in the beginning of the list.

    if (curr != head)

    {

        lastNode->next = head;

        newEnd = prev;

        prev->next = NULL;

        newHead = curr;

    }



    // Update new head of the linked list.

    newHead = curr;



    while (curr != lastNode)

    {

        if (curr->data % 2 == 1)

        {

            prev = curr;

            curr = curr->next;

        }



        // Move the even valued node to the end of the list.

        else

        {

            prev->next = curr->next;

            curr->next = NULL;

            newEnd->next = curr;

            newEnd = curr;

            curr = prev->next;

        }

    }



    // For handling the last node of the original linked list.

    if (newEnd != NULL and lastNode->data % 2 == 0)

    {

        prev->next = lastNode->next;

        lastNode->next = NULL;

        newEnd->next = lastNode;

    }



    // Return modified head.

    return newHead;

}

Accepted Answer

Iterative Approach 2

The idea is to split the linked list into two: one containing all odd valued nodes and others containing all the even valued nodes. And finally, attach the even node linked list after the odd node linked list.