Even reverse of a list

Question

The problem is taking a linked list and reversing the even nodes only. That is, a list 1->2->3->8 should become 1->8->3->2.

The solution I came up with traverses the list one and is constant in space. I believe that the problem has to be with copying the values of each node, rather than changing the pointers. They seem just not to be copied.

Here is the first version,

listnode * solve(listnode* A) {
    if(A == NULL || A->next == NULL)
        return A;

    listnode * current = A, * prev = NULL;
    size_t dim = 0;
    int nextVal, hasPrevious = 0;

    while(current != NULL) {
        dim++;
        

        if(dim % 2 == 0 && !hasPrevious) {
            prev = current; //We store the previous value
            hasPrevious = 1; //We now have a previous value
        }

        if(hasPrevious && dim % 2 == 0) {
            nextVal = current->val; //I store the value to plug it into previous
            current->val = prev->val; //Here I update next value with the previous value.
            prev->val = nextVal; //And now previous value has nextValue
            hasPrevious = 0; //We no longer have a previous value to copy
        }

        current = current->next;
    }

    return A;
}

The second solution is the same but using the -> operator when copying the values, but same result.

listnode * solve(listnode* A) {
    if(A == NULL || A->next == NULL)
        return A;

    listnode * current = A, * prev = NULL;
    size_t dim = 0;
    int nextVal, hasPrevious = 0;

    while(current != NULL) {
        dim++;
        //I work from the odd nodes such that I access the
        //other nodes deferencing the pointer, and thus
        //changing the content of the node.
        
        if(dim % 2 == 1 && !hasPrevious) {
            prev = current; //We store the previous value
            hasPrevious = 1; //We now have a previous value
        }

        if(hasPrevious && dim % 2 == 1) {
            nextVal = current->next->val; //I store the value to plug it into previous
            current->next->val = prev->next->val; //Here I update next value with the previous value.
            prev->next->val = nextVal; //And now previous value has nextValue
            hasPrevious = 0; //We no longer have a previous value to copy
        }

        current = current->next;
    }

    return A;
}

T

Answer 1

Assuming a -> b -> c -> d -> e -> f -> g -> h -> i -> j should become a -> j -> c -> h -> e -> f -> g -> d -> i -> b, (i.e. put all the nodes at even positions (counting from 1) in reverse order), I do not believe that can be done in a single pass through the list, at least for a singly linked list. It can be done in two passes.

The way I would implement it is as follows:

1. Extract the even nodes onto a new list.
2. Reverse the order of the nodes of the new list.
3. Merge the new list back into the original list.

Since it is easy to construct a list in reverse order from single nodes, steps 1 and 2 can be combined into a single step. So the two passes are:

1. Extract the even nodes onto a new list in reverse order.
2. Merge the new list back into the original list.

This solution reorders the list nodes by pointer manipulation rather than by swapping the values contained within nodes. I think this is what is normally expected when solving linked list problems.

Example implementation:

#include <stddef.h>
#include "listnode.h"

listnode *solve(listnode *A) {
    listnode *rev;
    listnode *el;
    listnode *ne;

    /*
     * First pass.
     *
     * Loop through pairs of nodes (el and ne) moving the second node
     * of each pair to a new list (rev) in reverse order.
     */
    rev = NULL;
    el = A;
    while (el != NULL && (ne = el->next) != NULL) {
        el->next = ne->next;
        el = ne->next;
        ne->next = rev;
        rev = ne;
    }

    /*
     * Second pass.
     *
     * Merge the reversed list of nodes (second node of each pair in reverse
     * order) back into the original list.
     */
    el = A;
    while (rev != NULL) {
        ne = rev;
        rev = ne->next;
        ne->next = el->next;
        el->next = ne;
        el = ne->next;
    }

    /* Return start of reordered list. */
    return A;
}