問題
次のように定義される連結リストに対して，指定された要素を削除する関数を書け．
1
2
3
4
5
| # Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
|
関数の引数と返り値は次の通り．
1
2
| def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
pass
|
例：
1
2
3
| head = [1] -> [2] -> [6] -> [3] -> [4] -> [5] -> [6]
val = 6
ans = [1] -> [2] -> [3] -> [4] -> [5] -> [6]
|
解法
- 単連結リストは「1つ次」が追えるデータ構造
- つまり
currがあればcurr.nextが取れる（当たり前） - その代わり1つ前が取れないので，追跡したいならそれ用の変数を用意しておく必要がある
- 単連結リストでの要素の削除は，「
currを削除したいなら，prevの次を（currを飛ばして）curr.nextにする」で実現される - 1つ前を追跡したいので
prevを考えるが，headの1つ前はどうしようか，となり，dummy_headを用意すればいいじゃないか，と至る．
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| # 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: Optional[ListNode], val: int) -> Optional[ListNode]:
if head is None:
return None
dummy_head = ListNode(val=-1, next=head)
prev = dummy_head
curr = head
while curr is not None:
if curr.val == val:
prev.next = curr.next
curr = curr.next
else:
curr = curr.next
prev = prev.next
return dummy_head.next
|
出典