[Leetcode] Delete Node/Remove Element in a Linked

Cruise_Chan 發布于2019-08-14 12:24 / 1528人閱讀

摘要：賦值法復雜度時間空間思路乍一看沒法獲取上一個鏈表節點，似乎無法將當前結點去除。實際上只要將下一個節點的值覆蓋當前節點，然后刪除下一個節點就好了。注意這樣不適用于尾節點。

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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