# LeetCode Easy 203. Remove Linked List Elements

tags: leetcode

問題

• Explore
• Problems

アイデア

｢valという値を連結リストから取り除け｣という問題です．

やるだけです．

解法

• 先頭からvalと同じ値を持つノードを取り除きます．
• 問題の連結リストは単方向連結リストなので，node1->node2->node3->...と繋がっている際に，node1を削除するにはその前のノードが必要です．
• そのため，ダミーのヘッドを作り，その先頭を指す変数cur_nodeを作ります．
• cur_nodeの次のノードの値がvalと同じならば，cur_nodeを次の次のノードに繋ぎます．
  • これによって，valと同じ値を持つノードを取り除くことが出来ます．

計算量

リストの大きさを$N$とする．

• 時間計算量
  • $O(N)$
• 空間計算量
  • $O(1)$

Python

# 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, val: int) -> ListNode:
        dummy_head = ListNode(0)
        dummy_head.next = head
        cur_node = dummy_head
        
        while cur_node.next:
            if cur_node.next.val == val:
                cur_node.next = cur_node.next.next
            else: 
                cur_node = cur_node.next
        return dummy_head.next