单链表 - 删除中间

我试图找出一种算法从一个链表中删除..单链表 - 删除中间

我的想法是遍历列表，找到我想要的节点之前的节点权删除，将其称为Nprev，并将Nprev设置为Nnext，其中Nnext位于要删除Ndelete的节点之后。因此Nprev -> Ndelte -> Nnext。

我的问题是，我无法弄清楚如何遍历这个列表来找到我想要的节点之前的节点。

我一直在做这个与seg故障，因为我分配的指针超出我假设的范围。它是一个非常凌乱的算法，我有很多if else语句。

有没有更简单的方法来做到这一点？

基本上我需要通过列表，对每个节点应用一个函数来测试它是否为真。如果为false，则删除该节点。删除第一个和最后一个并不难，但中间难倒了我。

请让我知道是否有一些通用的方法来解决这个问题。我一直在网上冲浪，找不到我需要的东西。

我用这个：http://www.cs.bu.edu/teaching/c/linked-list/delete/

但第4步之前的算法只删除第一个节点在我的名单并没有做任何更多。我该如何修改？

他们也给出了一个递归的例子，但我不明白它，并被它吓倒。

来源

2011-03-14 sanko

我建议你看看同一页面上的迭代示例。也许你会认为一个更容易？ – 2011-03-14 21:00:45

首先你需要找到中间节点。好吧，快速移动3个指针，缓慢，前进快速移动，慢两倍的速度，并prev存储缓慢的前一个节点的地址。即 *slow=&head,*fast=&head,prev=Null 遍历列表，当fast=NULL 如果元素个数为奇数且prev将存储中间节点的前一个节点的地址，则slow指向中间节点。如此简单 prev->next=slow->next。

来源

2012-08-10 21:42:28

这里的东西一个例子，我用它来搜索和索引中删除：

鉴于这种结构：（也适用于其他自参照结构）

struct node 
{ 
    S s; 
    int num; 
    char string[10]; 
    struct node *ptr; 
}; 
typedef struct node NODE;

使用此可以从列表中的某个位置删除某个项目（按索引）

int remove_by_index(NODE **head, int n) /// tested, works 
{ 
    int i = 0; 
    int retval = -1; 
    NODE * current = *head; 
    NODE * temp_node = NULL; 

    if (n == 0) { 
     return pop(head); 
    } 

    for (int i = 0; i < n-1; i++) { 
     if (current->ptr == NULL) { 
      return -1; 
     } 
     current = current->ptr; 
    } 

    temp_node = current->ptr; 
    retval = temp_node->num; 
    current->ptr = temp_node->ptr; 
    free(temp_node); 

    return retval; 

}

来源

2015-07-21 15:46:55 ryyker

单链表 - 删除中间

回答

相关问题