 # Suggesting another solution to 8.12(Even-Odd Merge)

#1

I came up with a solution based on turns.

I think this solution is less error-prone and easier.
The test passes, but please let me know how it looks.

Thanks!

``````shared_ptr<ListNode<int>> EvenOddMerge(const shared_ptr<ListNode<int>>& L) {
if(L == nullptr) {
return L;
}

shared_ptr<ListNode<int>> even_dummy(new ListNode<int>),
odd_dummy(new ListNode<int>);
array<shared_ptr<ListNode<int>>, 2> tails;
tails = even_dummy, tails = odd_dummy;
int turn = 0;
auto iter = L;

while (iter) {
tails[turn]->next = iter;
tails[turn] = tails[turn]->next;
turn ^= 1;
iter = iter->next;
}

if (turn == 1) { //last node was an even node
tails->next = nullptr;
}
tails->next = odd_dummy->next;

return even_dummy->next;
}``````
0 Likes

#2

Hey Eric,

Great, it definitely looks like a better approach. Like you said, it is less error-prone in terms of idea and implementation.

Thanks for sharing this great approach!

0 Likes

#3

Hi,

Currently the proposed solution to even-odd merge question in the book uses turns as Eric suggested, thanks for sharing it.

I’ve implemented it as below and test passes :

``````    public static ListNode<Integer> evenOddMerge(ListNode<Integer> L) {
if (L == null) return L;

ListNode<Integer> pEven = L;
ListNode<Integer> pOdd = L.next;

while (pEven.next != null && pOdd.next != null) {
pEven.next = pEven.next.next;
pEven = pEven.next;

pOdd.next = pOdd.next.next;
pOdd = pOdd.next;
}