【剑指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 }

巴特西

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

最新文章

热门文章