Sorting LinkedList with even after odd elements

Question

I am trying to solve this question : "Arrange elements in a given Linked List such that, all even numbers are placed after odd numbers. Respective order of elements should remain same."

This is the code I am using :

class Node<T> {
    T data;
    Node<T> next;
    Node(T data) {
        this.data = data;
    }
}

This is the main logic :

static Node<Integer> sortOddEven(Node<Integer> head) {
    if(head == null || head.next == null) {
        return head;
    }

    Node<Integer> middle = getMiddle(head);
    Node<Integer> nextOfMiddle = middle.next;

    middle.next = null;

    Node<Integer> temp1 = sortOddEven(head);
    Node<Integer> temp2 = sortOddEven(nextOfMiddle);

    Node<Integer> sortedList = sortOddEvenMerger(temp1, temp2);
    return sortedList;
}

static Node<Integer> sortOddEvenMerger(Node<Integer> head1, Node<Integer> head2) {
    Node<Integer> head3 = null, tail3 = null;

    if(head1.data.intValue()%2 != 0) {
        head3 = head1;
        tail3 = head1;

        head1 = head1.next;
    } else {
        head3 = head2;
        tail3 = head2;

        head2 = head2.next;
    }

    while(head1 != null || head2 != null) {

        if(head1 == null) {
            tail3.next = head2;

            return head3;
        } else if(head2 == null){
            tail3.next = head1;

            return head3;
        }

        if(head1.data.intValue()%2 != 0) {
            tail3.next = head1;
            tail3 = tail3.next;

            head1 = head1.next;
        } else {
            tail3.next = head2;
            tail3 = tail3.next;

            head2 = head2.next;
        }

    }

    tail3.next = null;

    return head3;
}

Basically I have tweaked MergeSort algorithm a little bit to solve this one, if I encounter odd elements , I add them first in the sortOddEvenMerger method and even elements after them. But the relative order of elements get changed.

Example : Input - 1 4 5 2

Expected output - 1 5 4 2

My output - 1 5 2 4

How can I tweak it more to maintain the relative order?

Answer 1

Your approach is not only making the problem more difficult than it is but is also more inefficient since if I'm understanding it correctly it is O(nlgon). This is because you're trying to implement mergesort algorithm and you sort the odd (and even)-elements which leads to wrong results.

A simple algorithm:

• Make two new lists (one for odd one for even elements) which are initially empty.

• Traverse the main list and add every odd element you find in odd list and every even element in even list. This is O(n) for traversal and O(1) for each insertion in each lists.

• When no elements are left in main list you have two lists odd-even with elements having right order so just link them to get one list with expected output- this step is O(1) as well!

Total complexity: O(n). (where n the length of main list).