Skip to main content
Hashnode不工程的攻城獅

Command Palette

Search for a command to run...

LeetCode Solution, Easy, 203. Remove Linked List Elements

刪除連結序列元素

Published
攻
攻城獅
Part of seriesLeetCode Solution

203. Remove Linked List Elements

題目敘述

Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head. Example 1:

removelinked-list.jpg

Input: head = [1,2,6,3,4,5,6], val = 6
Output: [1,2,3,4,5]

Example 2:

Input: head = [], val = 1
Output: []

Example 3:

Input: head = [7,7,7,7], val = 7
Output: []

Constraints:

  • The number of nodes in the list is in the range [0, 10**4].
  • 1 <= Node.val <= 50
  • 0 <= val <= 50

題目翻譯

給一個連結序列，從中刪除相同值的節點。

解法解析

這題的解法也是很基本的就是要遍歷所有的節點，跟題目 206 一樣，分別都會有迭代和遞迴的方式來解。主要是迭代的解法中，我們在前面多加一個 sentinel 節點，減少需要針對起始節點做判斷，今天如果起始節點是要刪除的元素的時候會比較麻煩。所以在開頭多加一個節點就可以把全部的序列都以同樣的條件去判斷和處理。

解法範例

Go

Recursive
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeElements(head *ListNode, val int) *ListNode {
    if head == nil {
        return nil
    }
    head.Next = removeElements(head.Next, val)
    if head.Val == val {
        return head.Next
    }
    return head
}
Sentinel node
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeElements(head *ListNode, val int) *ListNode {
    var sentinel = &ListNode{Next: head}
    var prev *ListNode = sentinel
    var curr *ListNode = head
    for curr != nil {
        if curr.Val == val {
            prev.Next = curr.Next
        } else {
            prev = curr
        }
        curr = curr.Next
    }
    return sentinel.Next
}

JavaScript

Recursive
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var removeElements = function (head, val) {
    if (!head) return null;
    head.next = removeElements(head.next, val);
    return head.val === val ? head.next : head;
};
Sentinel node
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var removeElements = function (head, val) {
    const sentinel = new ListNode(0, head);
    let prev = sentinel,
        curr = head;
    while (curr) {
        if (curr.val === val) {
            prev.next = curr.next;
        } else {
            prev = curr;
        }
        curr = curr.next;
    }
    return sentinel.next;
};

Kotlin

Recursive
/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun removeElements(head: ListNode?, `val`: Int): ListNode? {
        if (head == null) return null
        head.next = removeElements(head.next, `val`)
        return if (head.`val` == `val`) head.next else head
    }
}
Sentinel node
/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun removeElements(head: ListNode?, `val`: Int): ListNode? {
        var sentinel = ListNode(0)
        sentinel.next = head
        var prev = sentinel
        var curr = head
        while (curr != null) {
            if (curr.`val` == `val`) {
                prev.next = curr.next
            } else {
                prev = curr
            }
            curr = curr.next
        }
        return sentinel.next
    }
}

PHP

Recursive
/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val = 0, $next = null) {
 *         $this->val = $val;
 *         $this->next = $next;
 *     }
 * }
 */
class Solution
{

    /**
     * @param ListNode $head
     * @param Integer $val
     * @return ListNode
     */
    function removeElements($head, $val)
    {
        if ($head == null) {
            return null;
        }
        $head->next = $this->removeElements($head->next, $val);
        return $head->val == $val ? $head->next : $head;
    }
}
Sentinel node
/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val = 0, $next = null) {
 *         $this->val = $val;
 *         $this->next = $next;
 *     }
 * }
 */
class Solution
{

    /**
     * @param ListNode $head
     * @param Integer $val
     * @return ListNode
     */
    function removeElements($head, $val)
    {
        $sentinel = new ListNode(0, $head);
        $prev = $sentinel;
        $curr = $head;
        while ($curr != null) {
            if ($curr->val == $val) {
                $prev->next = $curr->next;
            } else {
                $prev = $curr;
            }
            $curr = $curr->next;
        }
        return $sentinel->next;
    }
}

Python

Recursive
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeElements(self, head: ListNode | None, val: int) -> ListNode | None:
        if head is None:
            return None
        head.next = self.removeElements(head.next, val)
        return head.next if head.val == val else head
Sentinel node
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeElements(self, head: ListNode | None, val: int) -> ListNode | None:
        sentinel = ListNode(0, head)
        prev, curr = sentinel, head
        while curr:
            if curr.val == val:
                prev.next = curr.next
            else:
                prev = curr
            curr = curr.next

        return sentinel.next

Rust

Swift

Recursive
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func removeElements(_ head: ListNode?, _ val: Int) -> ListNode? {
        guard head != nil else {
            return nil
        }
        head!.next = removeElements(head!.next, val)
        return head!.val == val ? head!.next : head
    }
}
Sentinel node
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func removeElements(_ head: ListNode?, _ val: Int) -> ListNode? {
        var sentinel = ListNode(0, head)
        var prev = sentinel
        var curr = head
        while curr != nil {
            if curr!.val == val {
                prev.next = curr!.next
            } else {
                prev = curr!
            }
            curr = curr!.next
        }
        return sentinel.next
    }
}
#leetcode#programming#programming-blogs#learn-coding

Comments

Join the discussion

No comments yet. Be the first to comment.

LeetCode Solution

Part 20 of 50

A collection of leetcode solustion

Up next

LeetCode Solution, Easy, 206. Reverse Linked List

反轉連結序列

More from this blog

如何開始入門軟體工程領域 - 名詞解釋（長期更新）

現在應該開始有很多人想要踏入軟體工程的領域，但在進入這個領域之前，覺得先了解一些名詞，可以在入門時更有方向也更知道要用什麼關鍵字去找尋有用的資訊。這篇文章就是想要幫助想要入門的人理解一些軟體工程裡的專有名詞。 作業系統 這一區塊主要解釋跟作業系統層面相關的名詞 英文中文解釋 Operation system 簡稱 OS | 作業系統 | 就是電腦的作業系統，是三大作業系統分別是：Linux、Windows、macOS | | Linux | | 自由和開放原始碼的 UNI...

May 10, 2023

我的 MacBook Pro (Apple Silicon) 設定

現在開始因為 ChatGPT 的出現，各種 AI 助手的功能都跑出來了。想想自己用了許久的環境設定也應該要來重新審視和建立新的開發環境了，僅此紀錄我個人的環境配置步驟和設定。 環境前置步驟 還原 MacBook Pro 至全新環境 macOS（全部資料刪除） 設定好初始設定後，登入 Apple ID 進入 App Store 確定 macOS 版本和預設 APP 都更新到最新 macOS 版本 到系統設定調整所有設定至個人習慣的設定 三指拖移 觸控板手勢開啟 防火牆開啟 輸入法設定...

Apr 25, 2023

ChatGPT 下的發展預想

從 ChatGPT 問世到現在，有許許多多的文章和討論出來。先從最早的 Google 要完蛋了，到後來的工作要被取代了，工程師失業了。 我就比較沒有想要馬上出來評論一下，我喜歡讓子彈飛一會兒。跟討論一下我自己比較在意的討論點。 Google 為什麼慢了? 結論：因為他需要更小心 很多人說 Google 怎麼被微軟搶先了一步。剛開始 Bing 說要加上 AI 的時候大家都在說 Google 怎麼慢了。我就馬上跑去看 OpenAI 的網站，靠北呀啊就 Azure 贊助的。那當然在正式上線 ChatG...

Mar 23, 2023
不

不工程的攻城獅

223 posts

I am not a programmer because I am not good at programming. But I do programming. Love to learn new things. An animal lover and a dancer. My oshi is 潤羽るしあ.