單鏈表 - 刪除中間

我試圖找出一種算法從一個鏈表中刪除..單鏈表 - 刪除中間

我的想法是遍歷列表，找到我想要的節點之前的節點權刪除，將其稱爲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

單鏈表 - 刪除中間

回答

相關問題