本文共 1400 字，大约阅读时间需要 4 分钟。
题目：
给定单向链表的头指针和一个结点指针，定义一个函数在O(1)时间删除该结点。/* 既然要在O（1）时间内删除，就不需要遍历，或者说大多数情况下不需要遍历整个链表，那么在O(1) 时间内我们能得到哪些东西呢？ 1.首先头指针和头指针下一个节点显然没有什么用，再者就是2. 需要删除的节点p和他的下一个节点next， 那么肯定是围绕着p和next操作。如果要删除应该链表节点，通常要找到它的前驱，这一道题能够构成这种前后关系的就是删除next，它的前驱是p，于是我们把next的东西复制给p，再删除next就ok了。以上是普通情况
当p是头结点时候，要特判，p是尾节点时候，只能够遍历整个链表了 此外，因为o（1）时间的限制，我们不能确保链表中有p，这只能交给函数调用者处理了void deleteNode(ListNode **pHeadList, ListNode *pToDeleteNode) { if (!(*pHeadList) || !pToDeleteNode) return; if (*pHeadList == pToDeleteNode) { // 删头节点 ListNode *temp = *pHeadList; if (temp -> next == NULL) { // 链表只有一个节点 *pHeadList = NULL; delete temp; } else { // 链表有其他节点 *pHeadList = (*pHeadList) -> next;// 不要使用delete (*pHeadList)，在没有被分配之前里面的内容还是完好的。// 而且delete不负责将指针设置为NULL。 delete temp; temp = NULL; } } else if (pToDeleteNode -> next != NULL) { // 在中间删除，把next值给当前节点， // 并且删除next ListNode *temp = pToDeleteNode -> next; pToDeleteNode -> key = pToDeleteNode -> next ->key; pToDeleteNode -> next = pToDeleteNode -> next -> next; delete temp; temp = NULL; } else if (pToDeleteNode -> next == NULL) { // 删除尾节点，必须遍历 ListNode *p = *pHeadList; while (p -> next != pToDeleteNode) p = p -> next; p -> next = NULL; delete pToDeleteNode; pToDeleteNode = NULL; }} 转载地址：http://ihzzi.baihongyu.com/