💨

NeetCode 150 [Linked List]:easy

2025/01/22に公開

NeetCodeのSolutionを書いていく

Reverse Linked List

片方向リストのheadが与えられます。
リストを逆にして新しいリストを返しましょう。

Input: head = [0,1,2,3]

Output: [3,2,1,0]
Input: head = []

Output: []

制限

0 <= The length of the list <= 1000.
-1000 <= Node.val <= 1000

時間:O(n)
メモリ:O(1)

片方向リストだから、後ろからアクセスできないわけだね。
ということは前から順にアクセスしながら、新しい片方向リストに格納しないといけない。
ん、単純に格納していけばいいだけなんじゃ。。。

一番うしろを探してそのnextに一つ前を、と言う処理を繰り返せばいけそうだが、これだとO(n^2)になりそう。
ループを回しながら、nextに前のobjectを指定すれば良い?

引数にOptionalがついているのはなぜだ?再帰的に実行するのかな?

class Solution:
    prev_obj = None
    def reverseList(self, head):
        if not head:
            return head

        # 次のデータを上書きするのでコピーしておく
        next = head.next

        # 次のデータを自分自身にする
        head.next = self.prev_obj
        self.prev_obj = head
        if next is None:
            return head
        return self.reverseList(next)

これでいけた。
ただこれだとstackメモリが配列分必要になるので、メモリ消費はO(n)になっちゃうのか。

再帰的にではなく、単純にループでやればO(1)になるらしい。

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev, curr = None, head

        while curr:
            temp = curr.next
            curr.next = prev
            prev = curr
            curr = temp
        return prev

Optionalは罠だったか・・・

Merge Two Sorted Lists

ソート済みの2つの片方向リンクドリストが与えられます。
2つのリストのノードからなる新しいリストで構成されたリストを作り、ヘッドを返す。

Input: list1 = [1,2,4], list2 = [1,3,5]

Output: [1,1,2,3,4,5]

Input: list1 = [], list2 = [1,2]

Output: [1,2]

Input: list1 = [], list2 = []

Output: []

制約

  • 0 <= The length of the each list <= 100.
  • -100 <= Node.val <= 100

時間: O(n + m) nはlist1のサイズmはlist2のサイズ
メモリ:O(1)

これも一時領域を設けたうえでループでリストを更新していくイメージだねきっと。
そして最初の要素でループを開始するリスト(ベースリスト)を決めて、ベースリストに対してもう一つのリストの要素を頭から比較して間に格納していく。

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if not list1:
            if not list2:
                return None # ここで[]を返すとテストがとおらない。バグ?
            return list2
        if not list2:
            return list1

        head = None # 先頭を残しておく
        cur = None # 評価対象を保存
        other = None # 現在評価中ではない方のlistを保持

        if list1.val < list2.val:
            cur = list1
            head = cur
            other = list2
        else:
            cur = list2
            head = cur
            other = list1

        while cur.next is not None:
            if cur.next.val > other.val:
                temp = cur.next
                cur.next = other
                other = other.next
                other = temp
            else:
                cur = cur.next

        cur.next = other

        return head

いけた。
ずいぶん長くなってしまった。

再帰を使うのが一番キレイ。
でもメモリ使用量がO(n+m)

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if list1 is None:
            return list2
        if list2 is None:
            return list1
        if list1.val <= list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list1, list2.next)
            return list2

あー。でも解法のメモリ使用量O(1)のやつもきれい
そうかこんなに短くなるか。


class Solution:
    def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:
        dummy = node = ListNode()

        while list1 and list2:
            if list1.val < list2.val:
                node.next = list1
                list1 = list1.next
            else:
                node.next = list2
                list2 = list2.next
            node = node.next

        node.next = list1 or list2

        return dummy.next

Linked List Cycle

制約

You should aim for a solution with O(n) time and O(1) space, where n is the length of the given list.

リンクリストに再帰がある場合はtrueをそうではない場合はfalseを返す。
リンクリストを頭からチェックして、nextと同じかどうか調べれば良い。
ただそれだとO(n^2)になる。

head == head.next.nextが自分かどうか見ればいいだけか?
あー、これだと3つのノードでループしているときだけか。

next == head.next
もあり得るし

next == head.next.next.next
もあり得るか...

まだeasyなのに答え見ちゃった・・・ 🥲

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow, fast = head, head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False

一つポインタを進めるのと、2つポインタを進めるのを用意して、同じものが見つかればループしているし、Noneが見つかればループはないんだそうな。ううむ確かにそうか・・・

悔しい。

Discussion