LeetCode Delete Node in a Linked ListQuestion题目分析代码

Question

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node. Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.

题目

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

样例 给定1->2->3->4,和节点3,删除 3 之后,链表应该变为1->2->4。

分析

一般,删除链表节点需要前置节点,需要n的时间复杂度。但这里要实现1的复杂度。 看似很难,无法解决。其实很简单,我们转换思路,我们可以删除当前的节点的下一个节点,那么我们就删除下一个节点,不过,在删除之前,把下一个节点的值保存到当前节点就可以了,这样不久相当于删除了当前节点么?当然当头尾节点这样就行不通了。

代码

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Jimoer

在Java的反射中,Class.forName和ClassLoader的区别

最近在面试过程中有被问到,在Java反射中Class.forName()加载类和使用ClassLoader加载类的区别。当时没有想出来后来自己研究了一下就写下来...

1572
来自专栏性能与架构

如何方便的搜索JS复杂数组?

例如下面这个稍微复杂一点的数组 [ { IceCream: ['mint', 'chocolate'], Fruit: 'banana' }, { I...

3685
来自专栏ACM算法日常

Bessie的好牌(队列)- POJ 3629

Bessie is playing a card game with her N-1 (2 ≤ N ≤ 100) cow friends using a dec...

1233
来自专栏对角另一面

lodash源码分析之compact中的遍历

本文为读 lodash 源码的第三篇,后续文章会更新到这个仓库中,欢迎 star:pocket-lodash

2206
来自专栏架构说

题目:将链表的奇数位和偶数位调换组成新的链表

题目:将链表的奇数位和偶数位调换组成新的链表 原题链接: http://oj.leetcode.com/problems/swap-nodes-in-pairs...

5599
来自专栏LanceToBigData

Java集合源码分析(三)Vevtor和Stack

前言   前面写了一篇关于的是LinkedList的除了它的数据结构稍微有一点复杂之外,其他的都很好理解的。这一篇讲的可能大家在开发中很少去用到。但是有的时候也...

2556
来自专栏项勇

笔记72 | 将姓放在名的后面,排序按姓氏首字母排列的修改笔记

1875
来自专栏大史住在大前端

野生前端的数据结构基础练习(6)——集合

3.为Set类增加一个higher(element)方法,该方法返回比传入元素大的元素中最小的一个,并写一段代码来测试该功能。

1063
来自专栏jessetalks

C#集合类型大盘点

C#集体类型( Collections in C#)   集合是.NET FCL(Framework Class Library)中很重要的一部分,也是我们开发...

2927
来自专栏IT笔记

2016头条校招笔试题(LRU)算法之JAVA实现

操作系统中可以使用LRU(Least Recently Used)内存淘汰旧数据的策略,如果内存需要加载新数据但空间不足,则会按照最近访问时间进行排序,并将最老...

34110

扫码关注云+社区

领取腾讯云代金券