c-删除链接列表中M个节点之后的N个节点

Question

我写了一个C程序，用于删除m个节点之后的n个节点。我不明白为什么它不起作用。我使用的是头节点而不是头指针。使用头节点而不是头指针好吗？

这是我的代码：

#include<stdio.h>
#include<stdlib.h>
struct node
{
    int data;
    struct node *next;
};
struct node* create()
{
    struct node *head=malloc(sizeof(struct node));
    head->next=NULL;
    return head;
}
void insert(struct node *head,int x)
{
    struct node *temp=head;
    struct node *new=malloc(sizeof(struct node));
    new->data=x;
    new->next=NULL;
    while(temp->next!=NULL)
        temp=temp->next;
    temp->next=new;
}
void display(struct node *head) {
    struct node *temp=head->next;
    while(temp!=NULL)
    {
        printf("n%dn",temp->data);
        temp=temp->next;
    }
}
void skipMDeleteN(struct node *head,int m,int n)
{
    int i;
    struct node *cur=head->next;
    while(cur)
    {printf("djhfj");
        for(i=1;i<m,cur!=NULL;i++)
            cur=cur->next;
        if(cur==NULL) return;
        struct node *t=cur->next;
        for(i=1;i<=n;i++)
        {
            struct node *temp=t;
            t=t->next;
            free(temp);
        }
        cur->next=t;
        cur=t;
    }
}
int main()
{
    struct node *head=create();
    int i;
    for(i=1;i<=10;i++)
    {
        insert(head,i);
    }
    int m=2,n=2;
    skipMDeleteN(head,m,n);
    display(head);
}

Answer 1

修复如下：

for(i=1;i<m && cur != NULL;i++) //Replace ',' with &&
{
    cur=cur->next;
}
if(cur==NULL) return;
struct node *t=cur->next;
for(i=1;i<=n && t!=NULL;i++) // Check if t reaches end of node.
{
    struct node *temp=t;
    t=t->next;
    free(temp);
}

Answer 2

我修改了您的代码，可以使用头指针。

void skipMDeleteN(struct node *head,int m,int n)
{
    int i;
    struct node *cur=head->next; 
       // printf("djhfj");
        for(i=1;i<m&&cur!=NULL;i++)
            cur=cur->next;
        if(cur==NULL) 
            return;
        struct node *t=cur->next;
        for(i=1;i<=n&&t!= NULL;i++)
        {
            struct node *temp=t;
            t=t->next;
            free(temp);
        }
        cur->next=t;
 }

Answer 3

这里有一个替代实现，我认为它将简化您想要实现的功能。诀窍是使用包装器结构。

由此，我将把我的结构定义如下：

struct llnode {
  int item;
  struct llnode *next;
};
typedef struct llnode *Node;
struct linkedlist {
  Node front;
  int length; // Optional, useful for O(1) linked list length.
};
typedef struct linkedlist *LinkedList;

使得在遍历n个节点之后删除k个节点更加容易实现。

您实现列表的方式使许多实现和客户端交互非常混乱，而且过于复杂。使用包装器结构可以简化为一点抽象。现在，您的create函数如下所示。

LinkedList create_LinkedList( void ) {
  // Requests a block of memory from the memory pool for a struct linked list.
  LinkedList new_LinkedList = malloc( sizeof( struct linkedlist ) );
  // Determines whether we requested a valid block of memory.
  if ( new_LinkedList == NULL ) {
    // Handle the error appropriately.
  }
  // Mutates the fields of the new linked list structure.
  new_LinkedList->front = NULL;
  new_LinkedList->length = 0;
  return new_LinkedList;
}

要遍历链表n个节点并删除k个节点，这将与您实现它的方式类似。我只会实现删除节点功能，因为如果为您提供了删除节点的功能，则遍历链表和删除k个数字节点是非常直接的。其实施方式如下：

int delete_FrontNode( LinkedList list ) {
  // Checks pre conditions.
  assert( list != NULL ); // Ensure it is not a NULL pointer.
  // Determines whether the length is already 0.
  if ( list->length == 0 ) return -1;
  // Define a backup pointer to the front node.
  Node ptr = list->front;
  // Define the return value (the node item).
  int const ret = ptr->item;
  // Mutate the front of the linked list to point to the next node.
  list->front = list->front->next;
  // Free the original front node.
  free( ptr );
  // Decrement the length of the linked list.
  list->length -= 1;
  return ret;
}