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

class Solution:
    def reorderList(self, head: ListNode) -> None:
        if not head:
            return

        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        prev, curr = None, slow
        while curr:
            curr.next, prev, curr = prev, curr, curr.next

        first, second = head, prev
        while second.next:
            first.next, first = second, first.next
            second.next, second = first, second.next

Input: head = [0,1,2], k = 4
Output: [2,0,1]

class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if not head:
            return None
        if not head.next:
            return head

        old_tail = head
        n = 1
        while old_tail.next:
            old_tail = old_tail.next
            n += 1
        old_tail.next = head

        new_tail = head
        for i in range(n - k % n - 1):
            new_tail = new_tail.next
        new_head = new_tail.next

        new_tail.next = None

        return new_head

Input: root = [3,9,20,null,null,15,7]
Output: 2

class Solution:
    def minDepth(self, root):
        def dfs(root):
            if root is None:
                return 0
            if root.left is None:
                return 1 + dfs(root.right)
            elif root.right is None:
                return 1 + dfs(root.left)
            return 1 + min(dfs(root.left), dfs(root.right))

        return dfs(root)

Input: stones = [2,7,4,1,8,1]
Output: 1

def removeDuplicates(s: str) -> str:
    stack = []
    for char in s:
        if stack and stack[-1] == char:
            stack.pop()
        else:
            stack.append(char)
    return ''.join(stack)

Input: ransomNote = "a", magazine = "b"
Output: false

def canConstruct(ransomNote: str, magazine: str) -> bool:
    for char in ransomNote:
        index = magazine.find(char)
        if index == -1:
            return false
        magazine = magazine[:index] + magazine[index + 1:]
    return True

Input: nums = [1,2,3]
Output: 2
Explanation:
Only two moves are needed (remember each move increments or decrements one element):
[1,2,3]  =>  [2,2,3]  =>  [2,2,2]

class Solution:
    def minMoves2(self, nums: List[int]) -> int:
        ans = float('inf')
        minval = min(nums)
        maxval = max(nums)
        for i in range(minval, maxval + 1):
            sum_moves = 0
            for num in nums:
                sum_moves += abs(num - i)
            ans = min(ans, sum_moves)
        return int(ans)

Input: nums = [1,-2,3,-2]
Output: 3

def maxSubarraySumCircular(nums):
    def kadane(arr):
        current_sum = max_sum = arr[0]
        for num in arr[1:]:
            current_sum = max(num, current_sum + num)
            max_sum = max(max_sum, current_sum)
        return max_sum

    max_kadane = kadane(nums)
    total_sum = sum(nums)
    min_kadane = kadane([-num for num in nums])

    return max(max_kadane, total_sum + min_kadane if total_sum + min_kadane != 0 else max_kadane)

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output: 
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:

        def backtrack(comb, remain, curr, counter, results):
            if remain == 0:
                results.append(list(comb))
                return
            elif remain < 0:
                return

            for next_curr in range(curr, len(counter)):
                candidate, freq = counter[next_curr]

                if freq <= 0:
                    continue

                comb.append(candidate)
                counter[next_curr] = (candidate, freq - 1)
                backtrack(comb, remain - candidate, next_curr, counter, results)
                counter[next_curr] = (candidate, freq)
                comb.pop()

        results = []
        counter = Counter(candidates)
        counter = [(c, counter[c]) for c in counter]

        backtrack(
            comb=[], remain=target, curr=0, counter=counter, results=results
        )

        return results

Input: products = ["havana"], searchWord = "havana"
Output: [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]

def suggestedProducts(products, searchWord):
    products.sort()
    result = []
    prefix = ""
    for char in searchWord:
        prefix += char
        suggestions = [product for product in products if product.startswith(prefix)]
        result.append(suggestions[:3])
    return result

Input: n = 27
Output: true
Explanation: 27 = 3^3

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if n <= 0:
            return False
        while n % 3 == 0:
            n //= 3
        return n == 1

Input: root = [4,2,6,1,3]
Output: 1

class Solution:
    def __init__(self):
        self.inorderNodes = []

    def inorderTraversal(self, root):
        if not root:
            return
        
        self.inorderTraversal(root.left)
        self.inorderNodes.append(root.val)
        self.inorderTraversal(root.right)
    
    def minDiffInBST(self, root):
        self.inorderTraversal(root)
        
        minDistance = float('inf')
        for i in range(1, len(self.inorderNodes)):
            minDistance = min(minDistance, self.inorderNodes[i] - self.inorderNodes[i - 1])
        
        return minDistance

Input: nums = [3,6,5,1,8]
Output: 18

def maxSumDivThree(nums):
    total_sum = sum(nums)
    if total_sum % 3 == 0:
        return total_sum
    
    mod1 = [x for x in nums if x % 3 == 1]
    mod2 = [x for x in nums if x % 3 == 2]
    
    mod1.sort()
    mod2.sort()
    
    if total_sum % 3 == 1:
        if len(mod1) >= 1 and len(mod2) >= 2:
            return max(total_sum - mod1[0], total_sum - sum(mod2[:2]))
        if len(mod1) >= 1:
            return total_sum - mod1[0]
        if len(mod2) >= 2:
            return total_sum - sum(mod2[:2])
    
    if total_sum % 3 == 2:
        if len(mod2) >= 1 and len(mod1) >= 2:
            return max(total_sum - mod2[0], total_sum - sum(mod1[:2]))
        if len(mod2) >= 1:
            return total_sum - mod2[0]
        if len(mod1) >= 2:
            return total_sum - sum(mod1[:2])
    
    return 0