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 #
ソート済みの２つの片方向リンクドリストが与えられます。 ２つのリストのノードからなる新しいリストで構成されたリストを作り、ヘッドを返す。
例
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
一つポインタを進めるのと、２つポインタを進めるのを用意して、同じものが見つかればループしているし、Noneが見つかればループはないんだそうな。ううむ確かにそうか・・・
悔しい。
Reply by Email