年末ですね。
最近、エンジニアとしての基礎力を高めたくてLeetCodeを始めました。
理解が甘いと感じた内容をここでアウトプットしていきます。

今回は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を回しています。

私のコードよりずっとシンプルで素敵でした。
こういうコードをサラッと書けるようになりたいです。

ここまでお読みいただきありがとうございました！

参考