package structure; import Offer.ListNode; /*以O（1）的时间复杂度删除单向链表的节点*/ public class deleteNode { public ListNode deleteListNode(ListNode head,ListNode deleteNode){ if(deleteNode.next!=null){ ListNode next=deleteNode.next; deleteNode.val=next.val; deleteNode.next=next.next; }else { if(head==deleteNode){ head=null; }else { ListNode cur=head; while (cur.next!=deleteNode){ cur=cur.next; } cur.next=null; } } return head; } }
若想要删除链表的节点，我们就需要知道链表的前一个节点，如果要找到单向链表的前一个节点，就需要遍历链表，进行寻找，时间复杂度为O(n)，显然不满足题目要求。
所以，我们采用的方法是，如果待删除节点不是尾节点，我们把待删除节点的后一个几点的内容赋值该待删除节点，从而达到删除节点的要求。当待删除节点为尾节点时，还是要采用遍历的方式。
原文：https://www.cnblogs.com/UalBlog/p/10963598.html