【剑指offer】以o(1)复杂度删除啊链表的节点，C++实现（链表）

0.简介

本文是牛客网《剑指offer》刷题笔记。

1.题目

在O(1)时间内删除链表节点。

2.思路

前提条件：删除的节点在链表上；边界条件：链表不为空和节点不为空；删除非尾节点i：删除节点i的下一个节点j的内容复制到节点i，然后节点i的指针指向节点j的下一个节点，删除节点j；删除尾节点i：顺序遍历得到被删节点的前序节点，然后删除被删除节点，前序节点指向nullptr。

3.code

  1 void DeleteNode(ListNode** pListHead, ListNode* pToBeDeleted)
  2 {
  3     if(!pListHead || !pToBeDeleted)
  4         return;
  5 
  6     // 要删除的结点不是尾结点
  7     if(pToBeDeleted->m_pNext != nullptr)
  8     {
  9         ListNode* pNext = pToBeDeleted->m_pNext;
 10         pToBeDeleted->m_nValue = pNext->m_nValue;
 11         pToBeDeleted->m_pNext = pNext->m_pNext;
 12 
 13         delete pNext;
 14         pNext = nullptr;
 15     }
 16     // 链表只有一个结点，删除头结点（也是尾结点）
 17     else if(*pListHead == pToBeDeleted)
 18     {
 19         delete pToBeDeleted;
 20         pToBeDeleted = nullptr;
 21         *pListHead = nullptr;
 22     }
 23     // 链表中有多个结点，删除尾结点
 24     else
 25     {
 26         ListNode* pNode = *pListHead;
 27         while(pNode->m_pNext != pToBeDeleted)
 28         {
 29             pNode = pNode->m_pNext;
 30         }
 31 
 32         pNode->m_pNext = nullptr;
 33         delete pToBeDeleted;
 34         pToBeDeleted = nullptr;
 35     }
 36 }