本文共 1347 字，大约阅读时间需要 4 分钟。
题目：
给定单向链表的头指针和一个结点指针，定义一个函数在O（1）时间删除该结点。链表结点结构如下：
struct ListNode{ int value; ListNode *next;}; 思路： 这题不难，关键是能不能想到那个点上。
这题关键点不是删除给定指针对应的那个结点（如果这样，必须知道其前一个结点，显然O（1）时间无法完成）。
如果将后一个结点的值赋给前一个结点，然后删除后一个结点，就可以了。
#include需要说明的是，如果被删除的是最后一个，时间复杂度是O（n），不过平均复杂度仍然是O（1）。 如果删除的是头结点，因为删除的始终是下一个，所以不需要重新更新头结点。#include #include #include #include using namespace std;struct ListNode{ int value; ListNode *next; ListNode(int a){ value = a; next = NULL; }};void deleteNode(ListNode *head, ListNode *toBeDeleted){ if (!head || !toBeDeleted) return; if (toBeDeleted->next == NULL)//删除尾结点 { ListNode *p = head; if (head == toBeDeleted) { delete head; head = NULL; } while (p->next != toBeDeleted) p = p->next; p->next = NULL; delete toBeDeleted; return; } ListNode *nextOfDelete = toBeDeleted->next; toBeDeleted->value = nextOfDelete->value; toBeDeleted->next = nextOfDelete->next; delete nextOfDelete;}int main(){ ListNode *a1 = new ListNode(1); ListNode *a2 = new ListNode(2); ListNode *a3 = new ListNode(3); ListNode *a4 = new ListNode(4); ListNode *a5 = new ListNode(5); a1->next = a2; a2->next = a3; a3->next = a4; a4->next = a5; deleteNode(a1, a5); for (ListNode*p = a1; p; p = p->next) cout << p->value << " "; cout << endl; return 0;}
还要考虑一种情况，只有一个结点，被删除和头结点都指向该结点。
转载地址：http://iapmi.baihongyu.com/