题目概述

删除一个节点的普通方法

在无头的单链表中

我们知道，删除一个节点，需要找到该Del节点的前面一个节点Pre，然后找到删除节点Del的下一个节点Next

让Pre的指向下一个的指针指向Next即可

当然，不要忘了处理只有一个节点的情况

然而，该方法的时间复杂度为O(N)

在O(1)的情况下删除一个节点

由于函数需要传入头结点和删除的节点，我们可以将删除节点Del的下一个节点Next删除

在删除前，将Next节点的值赋值给Del，间接的实现了删除

注意：如果删除的情况是尾节点（Del->m_pnext == NULL），则还需要从头遍历进行删除

综合情况下，该算法的时间复杂度为O(1)

代码实现

#include<iostream> using namespace std; struct ListNode { int _data; ListNode* _next; }; typedef ListNode Node; void DeleteNode(Node** phead,Node* delNode) { if (phead == NULL || delNode == NULL) return; if (delNode->_next != NULL)//删除的节点不是尾节点 { Node* nextNode = delNode->_next; delNode->_next = nextNode->_next; delNode->_data = nextNode->_data; free(nextNode); nextNode = NULL; } else if (delNode == *phead)//删除的节点是唯一的节点 { free(delNode); delNode = NULL; *phead == NULL; } else//删除的节点是尾节点，但是不是唯一的 { Node* cur = *phead; while (cur->_next != delNode) cur = cur->_next; cur->_next = NULL; free(delNode); delNode = NULL; } }