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），不需要额外的空间，因此是一个常数。