C++程序 在给定位置删除链表节点

给定一个单向链表和一个位置，在给定位置上删除链表节点。

例子：

输入：位置=1,链表=8->2->3->1->7
输出：链表=8->3->1->7

输入：位置=0,链表=8->2->3->1->7
输出：链表=2->3->1->7

如果要删除的节点是根节点，直接删除它。要删除中间的节点，我们必须有一个指向要删除的节点之前的节点的指针。因此，如果位置不是零，我们运行循环位置-1次并得到指向前一个节点的指针。

下面是上面想法的实现。

//完整工作的C++程序，可在给定位置删除链表中的节点#include <iostream>using namespace std; //链表节点class Node{    public:    int data;    Node *next;}; //给定对列表头的引用（指针对指针）以及int，在列表的前面插入一个新节点void push(Node** head_ref, int new_data){    Node* new_node = new Node();    new_node->data = new_data;    new_node->next = (*head_ref);    (*head_ref) = new_node;} //给定对列表头的引用（指针对指针）和位置，删除给定位置处的节点void deleteNode(Node **head_ref, int position){         //如果链接列表为空    if (*head_ref == NULL)        return;         //存储头节点    Node* temp = *head_ref;     //如果需要删除头    if (position == 0)    {                 //改变头        *head_ref = temp->next;                 //释放旧头        free(temp);                    return;    }     //查找要删除节点的前一个节点    for(int i = 0; temp != NULL && i < position - 1; i++)        temp = temp->next;     //如果位置大于节点数    if (temp == NULL || temp->next == NULL)        return;     //节点temp->next是要删除的节点    //存储指向要删除的节点的下一个节点的指针     Node *next = temp->next->next;     //从链接列表中取消链接节点    free(temp->next); // 释放内存         //从列表中取消链接已删除的节点    temp->next = next;} //此函数从给定节点开始打印链表的内容void printList( Node *node){    while (node != NULL)    {        cout << node->data << " ";        node = node->next;    }} //驱动程序int main(){         //从空列表开始    Node* head = NULL;     push(&head, 7);    push(&head, 1);    push(&head, 3);    push(&head, 2);    push(&head, 8);     cout << "创建了链表：";    printList(head);    deleteNode(&head, 4);    cout << "在位置4删除后的链表：";   printList(head);    return 0;}

输出：

创建了链表： 8  2  3  1  7 在位置4删除后的链表： 8  2  3  1 

时间复杂度： O（n），其中n表示给定链表的长度。

辅助空间： O（1），不需要额外的空间，因此是一个常数。