使用尾指针删除单个链表的最后一个节点

我在C中创建了一个单向链表，它具有头部和尾部指针，头部指针指向SLL的起始节点，尾部指针指向SLL的最后一个节点。我不想使用头指针遍历列表的末尾来删除节点。有没有办法让我可以使用尾指针来删除SLL的最后一个元素？使用尾指针删除单个链表的最后一个节点

以下是节点添加功能。头部和尾部发起NULL。

void add_node_last(Node** head, Node** tail, int data) { 

    Node* new_node = (Node *) malloc(sizeof(Node)); 

    new_node -> data = data; 
    new_node -> ptr = NULL; 

    if(*head == NULL && *tail == NULL) { 
     *head = new_node; 
     *tail = new_node; 
     return; 
    } 

    (*tail) -> ptr = new_node; 

    *tail = new_node; 

}

要删除的第一个节点，下面的函数：

void del_first(Node **head) { 
    if(*head == NULL) { 
     return; 
    } 
    *head = (*head) -> ptr; 
    free(*head); 
}

来源

2017-08-05 Paresh Lomate

顺便说一句'free（* head）;'是错的。 – BLUEPIXY

@BLUEPIXY然后什么是正确的陈述？ –

'Node * temp = * head; * head =（* head） - > ptr; free（temp）;'如果成为'* head == NULL'，那么需要将tail设置为NULL。 – BLUEPIXY

您可以自由节点的内存，但只有一次。在第一次删除之后，尾部指针和倒数第二个节点的ptr将是无效指针。为了确保两个指针总是正确的，你需要遍历整个列表或者使它成为一个双向链表。

这是一个很长的说法否（谢谢@stark）。

来源

2017-08-05 17:18:22

尾指针和最后一个节点的ptr都是错误的。所以正确的答案只是“否” – stark

@stark如果尾部指向最后一个节点，你可以“释放（尾部）”;但是在没有遍历整个列表的情况下，无法在此之后更新尾部。 –

@stark我明白你的意思了。我读“删除”只是释放内存。但要真正删除节点，您将不得不遍历整个列表。我会更新答案。 –

为了让它在没有双向链表的情况下工作，你可以让尾部的下一个指针指向列表头部，然后遍历它直到你到达尾部之前的节点。一旦那里你可以NULL它的下一个指针，它将从列表中分离出原始的尾部。然后将尾部设置为当前节点，然后释放原始尾部。

void del_last(Node **head, Node **tail) { 
    struct node *new_head = *head; 
    struct node *current = *tail; 

    current->next = head; 

    while(current-> != *tail) //getting the node right before the original tail 
    { 
     current = current->next 
    } 

    current->next = NULL; //detaches original tail form list 

    free(**tail); //gets rid of original tail 
    **tail = current; // sets current node to tail pointer 
}

来源

2017-08-22 17:59:48 aatate98

使用尾指针删除单个链表的最后一个节点

回答

相关问题