372. 在O(1)时间复杂度删除链表节点

题目

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

Linked list is 1->2->3->4, and given node 3, delete the node in place 1->2->4

分析

题目中还给了一个例子,在1->2->3->4的单链表中,如果给了节点3的情况下,如何将链表原地更新成1->2->4

一般的单链表节点删除,我们都会从前一个节点开始更新,比如更新1->2->3->4,常规流程为(伪代码)

   2.next = 3.next
   delete 3

但这里参数只给了节点3,并且单链表无法回溯前一个节点,如何完成删除呢?很简单,既然2.next无法更新,那么我们就把2.next对应的节点改造成我们期望的节点即可,也就是将3变成4,同时舍弃4(常规流程是更新2.next,舍弃3)

代码


public class Solution {
    /*
     * @param node: the node in the list should be deletedt
     * @return: nothing
     */
    public void deleteNode(ListNode node) {
        // write your code here
        ListNode next = node.next;
        if (next == null) return ;
        node.val = next.val;
        node.next = next.next;
    }
}

Show Comments

Get the latest posts delivered right to your inbox.