说删链表节点,第一时间想到就是遍历整个链表,找到删除节点的前驱,改变节点指向,删除节点,但是,这样删除单链表的某一节点,时间复杂度就是O(n),不符合要求;
时间复杂度是O(n)的做法就不说了,看看O(1)的写法,看图:
删除节点,需要找到被删节点的前驱,上面的说明,交换数据后,要删的节点转换为被删节点的后一个节点,此时被删节点前驱可以知道,删除就很简单了
给出被删节点指针,O(1)时间内就可以有此方法删除节点,但是,如果,被删节点是链表最后一个节点,以上方法明显不在适用,不得不从头遍历:
这时就得从头遍历,只为找最后一个节点的前驱,就这唯一一个节点,找它的时间复杂度就是O(n),但平均时间复杂度为:
((n-1)*O(1)+O(n))/n
结果还是O(1),复合要求的,又但是,这里没有考虑要删除的节点是否在链表中,如果要判断有没有在链表中,又得遍历,结果时间复杂度有不在是O(1),
为了保证时间,被删的节点有没有在链表中,只能由人为的去控制;以下是代码段:
//在O(1)时间内,删除一个节点,函数如下 void DeleteNodeNumone(ListNode** phead,ListNode* pToBeDelete) { if (*phead == nullptr || pToBeDelete == nullptr) return; //删除非尾节点 if (pToBeDelete->_next != nullptr) { ListNode* temp = pToBeDelete->_next; pToBeDelete->_data = temp->_data; pToBeDelete->_next = temp->_next; delete temp; temp = nullptr; } //只有一个节点 else if (*phead == pToBeDelete) { delete pToBeDelete; pToBeDelete = nullptr; *phead = nullptr; } //最后一种,删除节点是尾节点 else { ListNode* cur = *phead; while (cur->_next != pToBeDelete) { cur = cur->_next; } delete pToBeDelete; pToBeDelete = nullptr; cur->_next = nullptr; } }
#pragma once typedef int DataType; class ListNode { public: ListNode(const DataType& x) :_data(x) , _next(NULL) {} public: DataType _data; ListNode* _next; }; class Slist { public: Slist() :_head(NULL) , _tail(NULL) {} ~Slist() { //析构函数,删除节点,删除全部 Destory(); } void Destory() { ListNode* begin = _head; while (begin) { ListNode* del = begin; begin = begin->_next; delete del; } } public: //尾插 void PushBack(const DataType& x) { if (_head == NULL) { _head = new ListNode(x); _tail = _head; } else { _tail->_next = new ListNode(x); _tail = _tail->_next; } } //查找 ListNode* Find(const DataType& x) { ListNode* tmp = _head; while (tmp) { if (tmp->_data == x) return tmp; else { tmp = tmp->_next; } } return NULL; } // //在O(1)时间内,删除一个节点,函数如下 void DeleteNodeNumone(ListNode** phead,ListNode* pToBeDelete) { if (*phead == nullptr || pToBeDelete == nullptr) return; //删除非尾节点 if (pToBeDelete->_next != nullptr) { ListNode* temp = pToBeDelete->_next; pToBeDelete->_data = temp->_data; pToBeDelete->_next = temp->_next; delete temp; temp = nullptr; } //只有一个节点 else if (*phead == pToBeDelete) { delete pToBeDelete; pToBeDelete = nullptr; *phead = nullptr; } //最后一种,删除节点是尾节点 else { ListNode* cur = *phead; while (cur->_next != pToBeDelete) { cur = cur->_next; } delete pToBeDelete; pToBeDelete = nullptr; cur->_next = nullptr; } } void print() { ListNode* begin = _head; while (begin) { cout << begin->_data << "->"; begin = begin->_next; } cout << "NULL" << endl; } public: ListNode* _head; ListNode* _tail; }; void Test() { Slist s1; s1.PushBack(5); s1.PushBack(2); s1.PushBack(3); s1.PushBack(2); s1.PushBack(1); s1.PushBack(6); s1.PushBack(7); s1.PushBack(9); s1.print(); ListNode* num =s1.Find(9); s1.DeleteNodeNumone(&s1._head, num); s1.print(); }测试结果:
赐教!