如何从 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]

我已经创建了包含节点的列表和由另外 2 个列表组成的列表结构。我已经尝试实现一个能够产生这个的序列，但是，在找到要放入新子列表的 nTh 节点后，我很挣扎，我如何更改它的 next 以指向正确的新 nTh 节点。

例如：假设我有一个较小的链表：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

您应该插入 current 列表，而不是总是插入第一个列表，并在每次插入后更新它以指向下一个列表。使用额外的指针很容易实现：

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; 行）重置为超级列表的开头，因此这确保了值以旋转方式插入到每个子列表中。

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

How to Create Alternating Sub List from List in C?

c

linked-list

sequence