编写一个函数,重新排列一个链表,将偶数位置的节点放在列表中奇数位置的节点之后,保持偶数和奇数的相对顺序。
我在 Sedgewick 所著的 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;
}