链表问题_在O(1)时间内删除链表节点

水深无声 2022-05-21 01:39 97阅读 0赞

题目：给定单向链表的头指针和一个节点指针，定义一个函数在O(1)时间内删除该结点。  
分析：对于删除单向链表中的节点，通常的思路：删除节点I之前，先从链表的头结点开始遍历到I前面的一个节点h，把h的next节点指向I的下一个节点j，再删除节点I，但是这样做的复杂度为O(n)。这里采用另外一种思路，把节点j的内容复制覆盖节点I,接下来再把节点I的next指向j的下一个节点，之后再删除节点j。

/*
      struct ListNode {
           int val;
            struct ListNode *next;
            ListNode(int x) :
                  val(x), next(NULL) {
            }
      };
    */
    /*常规方法O(n)的时间*/
      void DeleteNode(ListNode**phead, ListNode*pdelete)
      {
          if (!phead || !pdelete)
              return;
    
          if (*phead == pdelete)
          {
              ListNode* pnext = pdelete->next;
              delete pdelete;
              pdelete = NULL;
              *phead = pnext;
          }
          else
          {
              ListNode* pnode = *phead;
              while (pnode->next!=pdelete)
              {
                  pnode = pnode->next;
              }
              pnode->next = pdelete->next;
              delete pdelete;
              pdelete = NULL;
    
          }
      }
    
    /*O(1)的方法*/
    void DeleteNode(ListNode**phead, ListNode*pdelete)
      {
          if (!phead || !pdelete)
              return;
          if (pdelete->next != NULL)
          {
              ListNode* pnode = pdelete->next;
              pdelete->val = pnode->val;
              pdelete->next = pnode->next;
              delete pnode;
              pnode - NULL;
          }
          else if (*phead == pdelete)
          {
              delete pdelete;
              pdelete = NULL;
              *phead = NULL;
          }
          else
          {
              ListNode* pnode = *phead;
              while (pnode->next!=pdelete)
              {
                  pnode = pnode->next;
              }
              pnode->next = NULL;
              delete pdelete;
              pdelete = NULL;
          }
      }

说明：虽然最后一个节点的删除需要遍历整个链表，但是前n-1个节点的删除都可以在常数时间内完成，则在均摊的意义下复杂度为：\[(n-1)\*O(1)+O(n)\]/n=O(1)。