甚至列表的反向

Question

问题是采用链表并仅反转偶数节点。也就是说，列表 1->2->3->8 应该变成 1->8->3->2.

我想出的解法遍历表一，在space中是常量。我认为问题出在复制每个节点的值，而不是更改指针。他们似乎只是不能被复制。

这是第一个版本，

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;
}

第二个解决方案相同，但在复制值时使用 -> 运算符，但结果相同。

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

假设 a -> b -> c -> d -> e -> f -> g -> h -> i -> j 应该变成 a -> j -> c -> h -> e - > f -> g -> d -> i -> b，（即将所有节点以相反顺序放在偶数位置（从 1 开始计数）），我不相信可以通过列表一次完成，至少对于单向链表。可以分两次完成。

我的实现方式如下：

将偶数节点提取到新列表中。
反转新列表节点的顺序。
将新列表合并回原始列表。

由于从单个节点以相反顺序构造列表很容易，因此可以将步骤 1 和步骤 2 合并为一个步骤。所以这两个pass是：

以相反的顺序将偶数节点提取到新列表中。
将新列表合并回原始列表。

此解决方案通过指针操作而不是通过交换节点中包含的值来重新排序列表节点。我认为这是解决链表问题时通常预期的结果。

示例实现：

#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;
}

甚至列表的反向

Even reverse of a list

c

iteration

reverse

linked-list

singly-linked-list