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:

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
    }
}