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

Question

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

以下是节点添加函数。 head 和 tail 初始化为 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);
}

Answer 1

您可以释放节点的内存，但只能释放一次。第一次删除后，您的尾指针和倒数第二个节点的 ptr 将成为无效指针。为了确保两个指针始终正确，您需要遍历整个列表或使其成为双向链表。

说不的方法很长（感谢@stark）。

Answer 2

为了使其在不使其成为双向链表的情况下工作，您可以让尾部的 *next 指针指向列表的头部，然后遍历它直到到达尾部之前的节点。一旦到达那里，您就可以将其 *next 指针设为 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
}

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

Delete last node of single linked list using tail pointer

c

pointers

linked-list

singly-linked-list