LinkedList sort even after odd items

Question

I am trying to solve this question: "Arrange the elements in this Linked List so that all even numbers fit after the odd numbers. The corresponding order of the elements should remain the same."

This is the code I'm 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 slightly modified the MergeSort algorithm to solve this problem, if I encounter odd elements, I add them first to the sortOddEvenMerger method and even the elements after them. But the relative order of the elements is changing.

Example: Input - 1 4 5 2

Expected Result - 1 5 4 2

My conclusion is 1 5 2 4

How can I tune it more to maintain relative order?

Answer 1

Your approach not only complicates the task, but is also more inefficient, because if I understand it correctly, it is O(nlgon) . This is because you are trying to implement the mergesort algorithm and sort the odd (and even) -elements, which leads to incorrect results.

Simple algorithm:

• Make two new lists (one for odd for even items) that are initially empty.

• Go through the main list and add every odd element that you find in the odd list, and every even element in the even list. This is O(n) for traversal and O(1) for each insert in each list.

• If there are no elements in the main list, you have two odd-even lists with the elements in the correct order, so just combine them to get one list with the expected output - this step is also O(1) !

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