c - 删除C中链表中的每个奇数位置节点

Question

我试图在 C 中创建一个函数来删除每个奇数位置的节点。例如 1,2,3,4 变成 2,4。

这是我尝试过的方法，但似乎不起作用。我在谈论 deletee 函数。我修改了它，但列表似乎没有变化。

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int val;
    struct node *next;
} node;

typedef struct ll {
    node *head;
} ll;

ll *newll() {
    ll *k = malloc(sizeof(ll));
    k->head = NULL;
    return k;
}

void insert(ll *l, int vl) {
    node *tmp = malloc(sizeof(node));
    tmp->next = NULL;
    tmp->val = vl;
    if (l->head == NULL) {
        l->head = tmp;
        return;
    }
    node *s = l->head;
    while (s->next != NULL)
        s = s->next;
    s->next = tmp;
}

void printll(ll *l) {
    node *s = l->head;
    while (s != NULL) {
        printf("%d ", s->val);
        s = s->next;
    }
}

void deletee(ll *l) {
    node *k = l->head;
    while (k != NULL && k->next != NULL) {
        node *tmp = k->next->next;
        k = tmp;
    }
}

int main() {
    ll *ll1 = newll();
    insert(ll1, 5);
    insert(ll1, 6);
    insert(ll1, 8);
    insert(ll1, 9);
    insert(ll1, 10);
    insert(ll1, 11);
    deletee(ll1);
    printll(ll1);
    return 0;
}

Answer 1

我们需要同时更新 ll.head 和 node.next，因此指向 node 的指针不够好，除非你想对头部进行特殊处理。相反，让我们使用指向我们要更新的指针的指针。

void delete_node(node** node_ptr_ptr) {
   node* to_delete = *node_ptr_ptr;
   *node_ptr_ptr = to_delete->next;
   free(to_delete);
}

void delete_every_second(ll* l) {
   node** node_ptr_ptr = &( l->head );
   while (1) {
      if (*node_ptr_ptr == NULL) break;
      delete_node(node_ptr_ptr);
      if (*node_ptr_ptr == NULL) break;
      node_ptr_ptr = &( (*node_ptr_ptr)->next );
   }
}

假设您从以下内容开始:

+------+      +------+      +------+      +------+
| head ------>| val  |  +-->| val  |  +-->| val  |
+------+      +------+  |   +------+  |   +------+
              | next ---+   | next ---+   | next --->NULL
              +------+      +------+      +------+

在 node** node_ptr_ptr = &( l->head ); 之后:

+------+      +------+      +------+      +------+
| head ------>| val1 |  +-->| val2 |  +-->| val3 |
+------+      +------+  |   +------+  |   +------+
    ^         | next ---+   | next ---+   | next --->NULL
    |         +------+      +------+      +------+
    |
    +-----+
          |
+------+  |
| ptr ----+
+------+

在 node* to_delete = *node_ptr_ptr; 之后:

              +------+
              | del ----+
              +------+  |
                        |
                 +------+
                 |
                 v
+------+      +------+      +------+      +------+
| head ------>| val1 |  +-->| val2 |  +-->| val3 |
+------+      +------+  |   +------+  |   +------+
    ^         | next ---+   | next ---+   | next --->NULL
    |         +------+      +------+      +------+
    |
    +-----+
          |
+------+  |
| ptr ----+
+------+

*node_ptr_ptr = to_delete->next 之后；免费(删除)；:

+------+                    +------+      +------+
| head -------------------->| val2 |  +-->| val3 |
+------+                    +------+  |   +------+
    ^                       | next ---+   | next --->NULL
    |                       +------+      +------+
    |      
    +-----+
          |
+------+  |
| ptr ----+
+------+

在 node_ptr_ptr = &( (*node_ptr_ptr)->next ); 之后:

+------+                    +------+      +------+
| head -------------------->| val2 |  +-->| val3 |
+------+                    +------+  |   +------+
          +---------------->| next ---+   | next --->NULL
          |                 +------+      +------+
          |
+------+  |
| ptr ----+
+------+