1

リンクされたリストを並べ替えて、リスト内の奇数の位置にあるノードの後に​​ノードを偶数の位置に配置し、偶数と奇数の両方の相対的な順序を維持する関数を作成します。

この問題は、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;
}
4

4 に答える 4