删除C中链表中每个奇数定位的节点 [英] Deleting every odd positioned node in a linked list in C

问题描述

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

I was trying to create a function in C that deletes every odd positioned node. For example 1,2,3,4 becomes 2,4.

这是我尝试过的方法，但似乎不起作用. 我在说deletee函数.我对其进行了修改，但列表似乎没有变化.

Here is what I tried but it doesn't seem to be working. Im talking about the deletee function. I modified it but the list doesn't seem to be changing.

#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;
}

推荐答案

我们需要同时更新ll.head和node.next，因此除非您有特殊情况，否则指向node的指针还不够好头部.相反，让我们使用指向我们要更新的指针的指针.

We'll need to update both ll.head and node.next, so a pointer to node isn't good enough unless you want to special case the head. Instead, let's use a pointer to the pointer we want to update.

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 );
   }
}

假设您从以下内容开始:

Say you start with the following:

+------+      +------+      +------+      +------+
| 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; free(to_delete);之后:

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

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

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

这篇关于删除C中链表中每个奇数定位的节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！