删除带头结点链表最后一个节点的数据结构算法

删除带头结点链表最后一个节点的算法可以分为两个步骤：

1. 找到倒数第二个节点。
2. 删除最后一个节点。

以下是 C++ 代码实现：

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

void deleteLastNode(ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return;
    }
    ListNode* p = head;
    ListNode* q = head->next;
    while (q->next != NULL) {
        p = q;
        q = q->next;
    }
    p->next = NULL;
    delete q;
}

首先判断链表是否为空或只有一个节点，如果是，则直接返回。然后定义两个指针 p 和 q，p 指向头结点，q 指向第一个真正的节点。从第一个节点开始，如果 q 的下一个节点不为空，就将 p 指向 q，q 指向 q 的下一个节点，一直循环直到 q 指向最后一个节点。此时，p 指向倒数第二个节点，q 指向最后一个节点。将 p 的 next 指针置为 NULL，即将倒数第二个节点的 next 指针指向 NULL，然后删除 q 节点即可。