c - 编写一个重新排列链表的函数，将偶数位置的节点放在列表中奇数位置的节点之后

Question

编写一个重新排列链表的函数，将链表中偶数位置的节点放在奇数位置的节点之后，同时保留偶数和奇数的相对顺序。

我在 Sedgewick 写的《Algorithm in c》一书中发现了这个问题。我尝试过但失败了。我试图将所有节点放在另一个链表上的偶数位置。很感谢你能帮助我。一个好主意就足够了。谢谢 :)。

这是我的 C 代码。

/*
 * File: rearranges.c <Exercise 3.36>
 * Note: Write a function that rearranges a linked list to put the nodes in even
 *       positions after the nodes in odd positions in the list, preserving the
 *       relative order of both the evens and the odds.
 *       NOTICE: I think it's necessary to use linked list with a dummy head.
 * Time: 2013-10-26 10:58
 */
#include <stdio.h>
#include <stdlib.h>

#define LEN 11

typedef struct node *link;
struct node {
    int  item;
    link next;
};

/* Traverse a linked list with a dummy head. */
void traverse(link t) {
    link x = t->next;

    while (x != NULL) {
        printf("%d ", x->item);
        x = x->next;
    }
    putchar('\n');
}

/* Detach even positon nodes from a linked list. */
link detach(link t) {
    link u = malloc(sizeof(*u));
    link x = t, y = u;

    /* x is odd position node. We should ensure that there's still one even
     * position node after x. */
    while (x != NULL && x->next != NULL) {
        y->next = x->next;
        x->next = x->next->next;
        x = x->next;
        y = y->next;
        y->next = NULL;
    }

    return u;
}

/* Combine two linked list */
link combine(link u, link t) {
    link x = u;
    link y = t->next;

    while (y != NULL) {
        link n = y->next;

        y->next = x->next;
        x->next = y;

        x = x->next->next;
        y = n;
    }

    return u;
}

/* The function exchanges the position of the nodes in the list. */
link rearranges(link t) {
    link u = detach(t);
    link v = combine(u, t);

    return v;
}

int main(int argc, char *argv[]) {
    int i;
    link t = malloc(sizeof(*t));
    link x = t;

    for (i = 0; i < LEN; i++) {
        x->next = malloc(sizeof(*x));
        x = x->next;
        x->item = i;
        x->next = NULL;
    }

    traverse(t);
    traverse(rearranges(t));

    return 0;
}

Answer 1

curr=head;
end=lastOfList;//last node if size of list is odd or last-1 node 

for(int i=1;i<=listSize()/2;i++)
{
     end->next=curr->next;
     end=end->next;
     end->next=null;
     if(curr->next!=null)
        if((curr->next)->next!=null)
           curr->next=(curr->next)->next;
    curr=curr->next;
}