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[0] = even_dummy, tails[1] = 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[1]->next = nullptr;
    }
    tails[0]->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;
    ListNode<Integer> oddHead = pOdd;

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

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

    pEven.next = oddHead;

    return L;
}

Is this similar to the older version of the solution? Should I consider this as error prone or not clear?

0 Likes