删除C中链表中的每个奇数位置节点
我试图在C中创建一个删除每个奇数定位节点的函数。 例如1,2,3,4变为2,4 。
这是我尝试过但它似乎没有起作用。 我在谈论deleteefunction。 我修改了它，但列表似乎没有改变。
#include #include 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的指针不够好，除非你想要特殊情况下的头部。 相反，让我们使用指向我们想要更新的指针。
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; free(to_delete); *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 ----+ +------+
在你的这个代码中：
while(k!=NULL) { if(k->next!=NULL && k->next->next!=NULL) k->next=k->next->next; }
你有一个无限循环因为你没有改变循环中k的值。
另外：你必须先删除/释放k->next内存，否则你会得到内存泄漏。
我将其重写如下：
void deletee(ll *l) { if (l->head == NULL) return; node* tmp = l->head; l->head = l->head->next; // skip first item free(tmp); node* k=l->head; while(k!=NULL && k->next!=NULL) { tmp = k->next; k->next = k->next->next; free(tmp); k = k->next; } }
结果（如预期）：
6 9 11
-
tmp存储下一个值以供将来删除 - 我们将下一个元素设置为待删除元素的下一个元素，以便后者被取消链接
- 我们免费
tmp - 然后我们跳到新的下一个元素并继续
您更改了deleteefunction的代码，但仍然不正确：
void deletee(ll *l) { node *k = l->head; while (k != NULL && k->next != NULL) { node *tmp = k->next->next; k = tmp; } }
您根本不修改列表。
这是一个带指针指针的解决方案，以避免列出空列表和列表中第一个节点的特殊情况。 k指向删除节点时必须更新的链接，除了在列表末尾之外，它在每次删除后被推送到保留的节点：
void deletee(ll *l) { node **k = &l->head; while (*k != NULL) { /* delete the node */ node *tmp = *k; *k = (*k)->next; free(tmp); if (*k != NULL) { /* skip the preserved node */ k = &(*k)->next; } } }