https://leetcode.com/problems/merge-two-sorted-lists/ ダミー Node を作って edge case の 空の Linked List が挿入されても大丈夫なようにする。 その後はループで l1 と l2 の val を比べ、 小さい値を tail.next に入れる。 その後、 next をずらす。 ループ後 l1, l2 のどちらかのリストが empty の場合、 Linked List に追加する必要があるので、 リストが empty か確認し、値があれば Linked List に追加する。 # Definition for singly-linked list. # class ListNode(object): # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution(object): def mergeTwoLists(self, l1, l2): """ :type l1: ListNode :type l2: ListNode :rtype: ListNode """ dummy = ListNode() tail = dummy while l1 and l2: if l1....

https://leetcode.com/problems/linked-list-cycle/ Linked List が Cycle なのかを確認する。 Linked List が Cycle な場合、 2つのポインターを使う。 (1つめのポインターは 1つずつ進み、 2つめのポインターは 2つずつ進む。) Cycle な場合どこかの時点で2つ進むポインター が1つしか進まないポインターに追いつくので Cycle だとわかる。 Cycle ではない場合 いずれかの時点で ポインターが Null になる。 Time complexity: O(n) Mem complexity: O(1) # Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def hasCycle(self, head): """ :type head: ListNode :rtype: bool """ slow, fast = head, head while fast and fast....

https://leetcode.com/problems/reverse-linked-list/ 考え方としては、 1 → 2 → 3 → 4 → 5 1 ← 2 ← 3 ← 4 ← 5 とするように考える。 回答方法は iterative なやり方と recursive なやり方がある。 iterative なやり方は 2つの pointer を使う。 prev と curr まず prev に　None を設定する。 curr は head にする Null → 1 → 2 → 3 → 4 → 5 ↑ ↑ prev curr ループしている間 Linked List の 矢印の向き (curr.next) をずらしつつ、prev と next の pointer もずらしていく。...

https://leetcode.com/problems/valid-parentheses/ Prerequisite Hash Map Stack 最初にどのカッコがどの 括弧閉じ にマッチしているかわかるために HashMap を作る必要がある。 この際、括弧閉じ をキーにする。 for 文で list の中を確認し、 括弧開きは stack に入れる。 stack は 最後に入れたものから出すので、 括弧開き と 括弧閉じ がマッチしていれば、 stack から pop できる。 最後に stack に何も残らなければ、 全てがマッチして True を return する。 Time complexity: O(n) Mem complexity: O(n) class Solution(object): def isValid(self, s): """ :type s: str :rtype: bool """ stack = [] closeToOpen = { ')' : '(', ']' : '[', '}' : '{' } for c in s: if c in closeToOpen: if stack and stack[-1] == closeToOpen[c]: stack....

https://leetcode.com/problems/missing-number/ sum([0,1,2,3]) - sum([3,0,1]) = 2 2がない数字なので、2が残る。 最初に result に len(nums) を代入する。 nums が [3,0,1] の場合、 result に 3 が代入される。 これは for で回す時に range(len(nums)) だと 0, 1, 2 としかならないため。 result に len(nums) の代入が必要。 result += (i - nums[i]) をすることで、2 が return 出来る。 Time complexity: O(n) Mem complexity: O(1) class Solution(object): def missingNumber(self, nums): """ :type nums: List[int] :rtype: int """ result = len(nums) for i in range(len(nums)): result += (i - nums[i]) return result