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?

Lieutenancy

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).

Ralina

Surely the last step is O(1) if you maintain a reference to the last Node in the odd list and the head of the even list? oddCurrent.next = evenHead (of course checks should be added to ensure oddCurrent != null, which is possible). I guess judging by what you said O(n) was a typo. – Cohere

Thanks fro comment!!! Actually I didn't to think at all since an O(n) at last step would not change the overall complexity but yes you're totally right !! (I'll edit the answer thanks again!!). – Ralina

in terms of big O no, but in practice yes. I'll delete my comment in a moment to keep the answer tidy, which was otherwise spot on. – Cohere

Totally agree, but I think this is a very useful comment it may be better to exist... – Ralina

Since we're leaving the comments, I should say that oddTail would be a better name than oddCurrent, but I can no longer edit. – Cohere

I agree this may make it more understandable :) !! – Ralina

Answer 2

Python code for this problem:

def evenAfterOdd(head):
    if head is None:
        return head
    end = head
    prev = None
    curr = head

    # Get pointer to last Node
    while (end.next != None):
        end = end.next

    new_end = end

    # Consider all even nodes before getting first odd node
    while (curr.data % 2 != 1 and curr != end):
        new_end.next = curr
        curr = curr.next
        new_end.next.next = None
        new_end = new_end.next

    # do following steps only if there is an odd node
    if (curr.data % 2 == 1):

        head = curr

        # now curr points to first odd node
        while (curr != end):

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

                prev = curr
                curr = curr.next

            else:

                # Break the link between prev and curr
                prev.next = curr.next

                # Make next of curr as None
                curr.next = None

                # Move curr to odd
                new_end.next = curr

                # Make curr as new odd of list
                new_end = curr

                # Update curr pointer
                curr = prev.next

    # We have to set prev before executing rest of this code
    else:
        prev = curr

    if (new_end != end and end.data % 2 != 1):
        prev.next = end.next
        end.next = None
        new_end.next = end
    return head

Blois

Code only answers are discouraged. Please provide a summary of how your answer solves the problem and why it may be preferable to the other answers already provided. – Herta