如何在C中从列表创建交替子列表

Question

假设我有一个具有以下结构的链表：

typedef struct _Node {
int value;
struct _Node *next;
} Node;
3 -> 0 -> 4 -> 5 -> 3 -> 2 -> 1 -> 11 -> NULL

我的目标是把它变成一个由不同的子列表按交替顺序组成的大列表。

这是本质上是"；列表列表"：

typedef struct _List {
Node *node;
struct _List *next;
} List;

我的最终目标是创建一个看起来像这样的东西：

// [] denotes a sub list not an array
[3 -> 5 -> 1 - > NULL] -> [0 -> 3 -> 11 -> NULL] -> [4 -> 2 -> NULL]

我已经创建了包含节点的列表和由另外两个列表组成的列表结构。我已经尝试过实现一个能够产生这种效果的序列，然而，在找到要放入新子列表中的第n个节点后，我正在努力，如何更改它的下一个节点以指向正确的新第N个节点。

例如：假设我有一个较小的链表：1 -> 5 -> 8 -> 10 -> NULL

当我将1添加到我的第一个子列表时，它仍然指向5，它仍然指8，依此类推。我的实际目标是1现在指向8，8指向NULL，然后在第二个子列表中，5将指向10，10指向NULL。

下面的代码有我想要的正确序列，并以这种方式打印出来，然而，我已经能够为链表的创建创建创建正确的代码。是否有任何方法或功能可以帮助实现此解决方案？

Node * list; // suppose that the head has a value of 3 which points to 0 and so on
List * bigList; // suppose that bigList points to 2 other lists in 
bigList -> node = list; // first node in first list points to the node list (3)
k = 3; // sub-lists that are created
size = 8; // number of nodes in the linked list

for(int i = 0; i < k; i++){
for(int j = i; j < size; j += k){
// here is where I would have to manipulate list and weave it into different sub lists
fprintf(stdout, "%d -> ", getNode(list, j) -> value); // prints correct sequence (getNode is a function that finds the nTh node in the list)
}
fprintf(stdout, "n");
}

Answer 1

与其总是插入到第一个列表中，不如插入到当前列表中，并在每次插入后更新该列表以指向下一个列表。这很容易通过一个额外的指针来实现：

void insert_node_into_list (Node ** list, int value) {
Node * node = malloc(sizeof *node);
*node = (Node) {.value = value, .next = NULL};
while (*list) list = &(**list).next;
*list = node;
}
void new_list (List ** superlist) {
// since we're creating all superlists at once, they can be inserted in any order
// so we do it at the front, since it's faster
List * list = malloc(sizeof *list);
*list = (List) {.node = NULL, .next = *superlist};
*superlist = list;
}
void insert_node_into_superlist (List * superlist, List ** current, int value) {
insert_node_into_list(&(**current).node, value);
*current = (**current).next;
if (!*current) *current = superlist;
}

现在你只需要像这样构建你的列表：

List * superlist = NULL;
unsigned x;
for (x = 0; x < 3; x ++) new_list(&superlist);
List * current = superlist;
insert_node_into_superlist(superlist, &current, 3);
insert_node_into_superlist(superlist, &current, 0);
insert_node_into_superlist(superlist, &current, 4);
insert_node_into_superlist(superlist, &current, 5);
insert_node_into_superlist(superlist, &current, 3);
insert_node_into_superlist(superlist, &current, 2);
insert_node_into_superlist(superlist, &current, 1);
insert_node_into_superlist(superlist, &current, 11);

current指针将始终指向用于插入的下一个子列表，因此它将遍历超级列表中的所有子列表。由于当它到达超级列表的末尾时(通过if (!*current) *current = superlist;行(，它被重置为超级列表的开头，这确保了值以旋转的方式插入到每个子列表中。