Start counting with the total number of questions finished.
Q44
Hard. Linked list
Use merge two sorted lists to merge the lists until there's only one left.
From Neetcode, youtube.com/watch?v=q5a5OiGbT6Q
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
# Edge case
if not lists:
return None
# Merge until there's only one left
while len(lists) > 1:
mergedLists = []
for i in range(0, len(lists), 2):
l1 = lists[i]
# Edge case
l2 = lists[i + 1] if (i + 1) < len(lists) else None
mergedLists.append(self.mergeList(l1, l2))
lists = mergedLists
return lists[0]
# Merge two
def mergeList(self, l1, l2):
dummy = node = ListNode()
while l1 and l2:
if l1.val <= l2.val:
node.next = l1
l1 = l1.next
else:
node.next = l2
l2 = l2.next
node = node.next
node.next = l1 or l2
return dummy.next
Q45
Hard. Linked list
class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
dummy = ListNode(0, head)
groupPrev = dummy
while True:
kth = self.getKth(groupPrev, k)
if not kth:
break
groupNext = kth.next
# Reverse group
prev, curr = kth.next, groupPrev.next
while curr != groupNext:
tmp = curr.next
curr.next = prev
prev = curr
curr = tmp
tmp = groupPrev.next
# Put the kth as the head of the reversed group
groupPrev.next = kth
# Assign new groupPrev
groupPrev = tmp
return dummy.next
def getKth(self, curr, k):
while curr and k > 0:
curr = curr.next
k -= 1
return curr
Q46
Easy. Tree
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
# Swap the children
tmp = root.left
root.left = root.right
root.right = tmp
self.invertTree(root.right)
self.invertTree(root.left)
return root
Or
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
right = self.invertTree(root.right)
left = self.invertTree(root.left)
root.left = right
root.right = left
return root