Linked ListをPythonで扱う #438
年末ですね。
最近、エンジニアとしての基礎力を高めたくてLeetCodeを始めました。
理解が甘いと感じた内容をここでアウトプットしていきます。
今回はLinked List (連結リスト)です。
Linked Listとは？
連結リスト（linked list）とは、基本的なデータ構造の一つで、複数のデータを格納することができ、各データが一つ前あるいは後（もしくはその両方）のデータへの参照情報（リンク、ポインタ）を持っている構造のこと。
つまり各データは、データそのものに加えて順番の情報を持っています。LeetCodeでは以下のようなクラスで定義されていました。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def __str__(self):
return f"ListNode{{val: {self.val}, next: {self.next}}}"valにデータそのものが入り、nextに次のListNodeが入ります。最後の要素だとnextがNoneになります。また、ここでは「次」の情報のみで、「前」の情報は持っていません。
例えば以下のようなデータになります。
node = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
print(node)
>> ListNode{val: 1, next: ListNode{val: 2, next: ListNode{val: 3, next: ListNode{val: 4, next: ListNode{val: 5, next: None}}}}}Linked ListをPythonで扱う
LeetCodeの問題文では、ランダムに生成されるLinked Listを半分にして後ろのリストだけ返す、という操作が必要でした。奇数の場合は真ん中の要素を含む形で返します。
私の最初の回答は以下です。
問題文を愚直にコードに落としており、整理したつもりですが、関数を循環させたことで処理が複雑になってしまっています。
import math
class Solution:
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
head_len = self.search_length(head)
median = head_len/2 + 1 if head_len % 2 == 0 else math.ceil(head_len / 2)
return self.build_result(head, median)
def search_length(self, next: Optional[ListNode], length = 0):
length += 1
if not next.next:
return length
else:
return self.search_length(next.next, length)
def build_result(self, head, median, count = 0):
count += 1
if count == median:
return head
else:
return self.build_result(head.next, median, count)他の方の回答例を見た中で、最も洗練されていると感じたのは以下です。
class Solution:
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
count = 0
dummy_head = head
while dummy_head is not None:
count += 1
dummy_head = dummy_head.next
for i in range(count // 2):
head = head.next
return head要素数を数えつつ、それを「// (切り捨て除算)」演算子で半分にし、rangeでforを回しています。
私のコードよりずっとシンプルで素敵でした。
こういうコードをサラッと書けるようになりたいです。
ここまでお読みいただきありがとうございました！