剑指offer----O(1)时间删除给定链表中的节点

偏执的太偏执、 2022-07-21 11:10 137阅读 0赞

如果从头开始遍历，遍历到给定节点的前一个节点，让它的前一个指向它的下一个，该节点指向为空，就把该节点删除掉了，但是这个时间复杂度为O(N);

思路：既然是给出了一个链表中的节点，我们可以根据这个节点的next属性找到它的下一个节点，让该节点的值和next都等于下一个节点的值和next就达到对下一个节点的复制，该节点的值和next都被覆盖掉了，然后把删除它的下一个节点，也就达到对给定节点的删除。

（1）链表中有多个节点删除的不是尾节点

（2）链表中只有一个节点，且删除这个节点

（3）删除链表的尾节点；

class ListNode 
    {
           int val;
           ListNode next = null;
    
          ListNode(int val) 
          {
              this.val = val;
          }
      }
    public class DeleteNode
    {
      public void deleteNode(ListNode pHead,ListNode toBeDeleted)
      {
    	  if(pHead==null || toBeDeleted==null)
    	  {
    		  return;
    	  }
    	  //如果要删除的节点不是最后一个节点，可以把要删除的节点的next val换成它下一个节点的内容
    	  if(pHead.next != null)
    	  {
    		ListNode  pNext = toBeDeleted.next;
    		toBeDeleted.val = pNext.val;
    		toBeDeleted.next = pNext.next;
    		pNext = null;
    	  }
    	  //链表中只有一个节点
    	  else if(pHead == toBeDeleted)
    	  {
    		  toBeDeleted = null;
    		  pHead = null;
    	  }
    	  //删除链表的尾节点 找到尾节点的前一个节点
    	  else
    	  {
    		  ListNode pre = pHead;
    		  while(pre.next != toBeDeleted)
    		  {
    			  pre = pre.next;
    		  }
    		  pre.next = null;
    		  toBeDeleted = null;
    	  }
      }
    }