【Everyday】(10)在O(1)时间复杂度删除链表节点 - Everyday - SegmentFault

【Everyday】(10)在O(1)时间复杂度删除链表节点 - Everyday - SegmentFault

给定一个单链表中的表头和一个等待被删除的节点(非表头或表尾)。请在在O(1)时间复杂度删除该链表节点。并在删除该节点后，返回表头。

样例
给定 1->2->3->4，和节点 3，返回 1->2->4

解题思路

这个题目在解决的时候的常规思路是从头开始遍历找到这个节点，同时保留其前面的一个节点，然后将其前面的节点指向后一个节点，然后将这个节点置为null即可，但是这种方式的复杂度是O(n)，我们要在O(1)的复杂度内解决该问题，需要我们直接通过给定的节点，然后找到其后面的一个节点，然后将后面的节点复制过来，然后使的其当前的下一个指向指向其后一个节点的指向即可。

实现代码

public void deleteNode(ListNode node) {          // write your code here          if(node==null)              return;          if(node.next==null)              node = null;          else if(node.next!=null){              node.val = node.next.val;              node.next = node.next.next;      }  }

优化与思考

代码看起来比较简洁，但是涉及到类似于指针的问题，在其指向上很容易出现一些问题，这里在写的时候，想到了要将其中的一个节点释放掉，结果释放了一个有用的节点，导致出现了问题。涉及类似指针指向的问题多加小心。

• 1 天前发布
• 更多

Read full article from 【Everyday】(10)在O(1)时间复杂度删除链表节点 - Everyday - SegmentFault