[Leetcode] Delete Node/Remove Element in a Linked

Cruise_Chan 发布于2019-08-14 12:24 / 1408人阅读

摘要：赋值法复杂度时间空间思路乍一看没法获取上一个链表节点，似乎无法将当前结点去除。实际上只要将下一个节点的值覆盖当前节点，然后删除下一个节点就好了。注意这样不适用于尾节点。

Delete Node in a Linked List

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) 空间 O(1)

思路

乍一看没法获取上一个链表节点，似乎无法将当前结点去除。实际上只要将下一个节点的值覆盖当前节点，然后删除下一个节点就好了。注意这样不适用于尾节点。

代码

public class Solution {
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

Remove Linked List Elements 伪造表头 复杂度

时间 O(N) 空间 O(1)

思路

删除链表所有的特定元素的难点在于如何处理链表头，如果给加一个dummy表头，然后再从dummy表头开始遍历，最后返回dummy表头的next，就没有这么问题了。

代码

public class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode curr = dummy;
        while(curr.next!=null){
            if(curr.next.val == val){
                curr.next = curr.next.next;
            } else {
                curr = curr.next;
            }
        }
        return dummy.next;
    }
}

私有云 GPU服务器 linked Element LeetCode LeetCode_String

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64449.html

LeetCode707：设计链表 Design Linked List

摘要：爱写设计链表的实现。单链表中的节点应该具有两个属性和。插入后，新节点将成为链表的第一个节点。将值为的节点追加到链表的最后一个元素。如果等于链表的长度，则该节点将附加到链表的末尾。如果索引有效，则删除链表中的第个节点。操作次数将在之内。爱写bug (ID:iCodeBugs) 设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是...

iliyaku 2019-08-16 18:34 评论0 收藏0
LeetCode707：设计链表 Design Linked List

摘要：爱写设计链表的实现。单链表中的节点应该具有两个属性和。插入后，新节点将成为链表的第一个节点。将值为的节点追加到链表的最后一个元素。如果等于链表的长度，则该节点将附加到链表的末尾。如果索引有效，则删除链表中的第个节点。操作次数将在之内。爱写bug (ID:iCodeBugs) 设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是...

FullStackDeveloper 2019-07-31 11:28 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月汇总（100 题攻略）

摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。一目录不折腾的前端，和咸鱼有什么区别...

tain335 2019-08-26 10:28 评论0 收藏0
[LeetCode] 426. Convert BST to Sorted Doubly Linke

Problem Convert a BST to a sorted circular doubly-linked list in-place. Think of the left and right pointers as synonymous to the previous and next pointers in a doubly-linked list. Lets take the foll...

MartinDai 2019-08-16 13:28 评论0 收藏0