LeetCode: Linked List

    A → B → C → D → None

    A → B → C → D → E  
            ↑       ↓  
            H ← G ← F

    def countNodes(head):
        count = 0
        curr = head
        
        while curr: 
            count += 1
            curr = curr.next

        return count

def removeNthFromEnd(head: Optional[ListNode], n: int) -> Optional[ListNode]:
    
    # dummy (sentinel) node used to point to the head
    dummy = ListNode(0, head)
    fast = slow = dummy

    # Move fast pointer n+1 steps ahead to keep gap
    for _ in range(n + 1):
        fast = fast.next

    # Move both pointers until fast reaches end
    while fast:
        fast = fast.next
        slow = slow.next

    # Remove the nth node (slow.next)
    slow.next = slow.next.next

    # Return head dummy is pointing to (may be different from original)
    return dummy.next 

    def findMiddle(head):
        slow = fast = head

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

        return slow

    # If F == None: Even length list
    # S points to start of right half
    # Left and right halves have equal length

    # If F != None: Odd length list
    # S points to middle node (belongs to left half) 
    # Left half is longer by 1 element

    # None                              S: None
    # S^F^                              F: None

    # 0     None                        S: 0
    # S^F^                              F: 0

    # 0   1   None                      S: 1
    #     S^  F^                        F: None

    # 0   1   2   None                  S: 1
    #     S^  F^                        F: 2

    # 0   1   2   3   None              S: 2
    #         S^      F^                F: None

    # 0   1   2   3   4   None          S: 2
    #         S^      F^                F: 4

    # 0   1   2   3   4   5   None      S: 3
    #             S^          F^        F: None

    # 0   1   2   3   4   5   6   None  S: 3
    #             S^          F^        F: 6

    def reverseList(head):
        prev = None
        curr = head

        while curr:
            next_node = curr.next
            curr.next = prev
            prev = curr
            curr = next_node

        return prev

    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        
        # Note:
        # With recursive Linked Lists:
        # A good way to think about the problem, is that you have access
        # to the list in reverse order, so what actions do you need to
        # take in order to reverse the list, while traversing the list
        # from back to front

        # Base case: 
        # If current list is empty or has only one node -> this node becomes the new head
        if head == None or head.next == None:
            return head

        # Recursion: reverse the rest of the list (head.next to end)
        # After Recursion: new_head is new head of reverse list (tail of original list)
        new_head = self.reverseList(head.next)

        # Recursion Part 1: Reverse Flow of next element (by adding head <- head.next)
        # After recursion: Point second Element to Original Head
        head.next.next = head

        # Recursion Part 2: Reverse Flow of curr element (by adding None <- head), as current head may be first element in original list
        # After recursion: point first element in original list to None
        head.next = None

        # Continue passing back new head (last element from original list), from the deepest recursive call

        # overall: time complexity O(n)
        # overall: space complexity O(n)
        return new_head 

    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        
        if not head or not head.next:
            return head

        new_head = self.reverseList(head.next)
        
        head.next.next = head
        head.next = None

        # overall: time complexity O(n)
        # overall: space complexity O(n)
        return new_head 

    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        
        # Setting prev pointing to None (end of reversed list)
        prev = None

        # Starting at head
        curr = head

        # while _ is not None
        # time complexity: iterate over list of n length O(n)
        while curr != None:

            # Grab next node, before disconnecting
            next_node = curr.next  

            # Disconnect and Reverse Flow: 
            # <- prev    curr -> next 
            # <- prev <- curr    next 
            curr.next = prev      

            # Advance both prev and curr
            prev = curr            
            curr = next_node       


        # Loop exits: 
        # val: (val)  (None)
        # node: prev -> curr

        # overall: time complexity O(n)
        # overall: space complexity O(1)
        return prev  

    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        
        prev = None
        curr = head

        while curr:

            next_node = curr.next  

            curr.next = prev      

            prev = curr            
            curr = next_node       

        # overall: time complexity O(n)
        # overall: space complexity O(1)
        return prev  

    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        
        # Note:
        # Building merged list from right to left,
        # connecting current node and passing back as we go
        
        # Base case: 
        # One of the lists is empty,
        # return second list for the .next
        if not list1:
            return list2
        if not list2:
            return list1

        # Recursive Call:
        # Point smaller val -> rest of list
        if list1.val < list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list1, list2.next)
            return list2

        # overall: time complexity O(n)
        # overall: space complexity O(n)

    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        
        # Note:
        # DummyHead is used to enter the iterative loop cleanly
        # without handling first node assigning case
        
        # sentinel anchor for real head
        dummyHead = ListNode(-1)  

        # curr node of list
        tail = dummy          

        # Traverse both lists while both have nodes
        # time complexity: iterate over both lists O(m + n)
        while list1 and list2:

            # grab smaller value between list1 and list2
            if list1.val < list2.val:
                
                # append and iterate list1
                tail.next = list1     
                list1 = list1.next   
            else:
                # append and iterate list2
                tail.next = list2
                list2 = list2.next    

            # 1st iteration: dummyHead/tail no longer point to same obj
            # nth iteration: iterate tail to whatever the next_node is
            tail = tail.next          

        # At least one list is non empty at this point:
        # point tail to rest of list
        if list1:
            tail.next = list1
        else 
            tail.next = list2

        # Jump to merged head using dummyHead

        # overall: time complexity O(m + n)
        # overall: space complexity O(1)
        return dummyHead.next

    def hasCycle(self, head: Optional[ListNode]) -> bool:
        
        # Note:
        # Track visited nodes to check for repeats (cycles)
        
        # Nodes are stored by obj reference,
        # perfect for cycle detection
        visited = set()

        # start of iteration
        curr = head
        
        # time complexity: iterate over list of n length O(n)
        while curr:

            # repeated node: (cycle detected)
            if curr in visited:
                return True

            # add and continue iteration
            visited.add(curr)
            curr = curr.next
        
        # no repeat nodes (no cycles)

        # overall: time complexity O(n)
        # overall: space complexity O(n)
        return False

    def hasCycle(self, head: Optional[ListNode]) -> bool:
        
        # Note:
        # If no cycle: fast pointer will hit None (end of list)
        # If cycle: once both fast and slow pointer enter cycle of size k,
        # fast pointer will lap and hit slow pointer within k steps

        # set pointers
        slow, fast = head, head
        
        # time complexity: iterate over list 
        while fast and fast.next:

            # move both slow and fast pointers
            slow = slow.next
            fast = fast.next.next
            
            # check if match (cycle detected)
            if slow == fast:
                return True

        # reached end of list (no cycle detected)
        
        # overall: time complexity O(n)
        # overall: space complexity O(1)
        return False

    def reorderList(self, head: Optional[ListNode]) -> None:

        # Note:
        # 1. Use Tortoise Hare to find the middle
        # 2. Reverse second half of list in place
        # 3. Merges first half and reverse second half alternating
        # Result: Fully in place reordering

        slow = fast = head
        while fast and fast.next:
            # slow travels half distance vs fast pointer
            slow = slow.next
            fast = fast.next.next

        # Slow result:
        # Odd List: slow -> odd mid
        # Even List: slow -> mid2

        # prev for reverse tail
        prev = None
        
        # Set Curr:

        # Odd List:
        # curr = slow.next, (mid.next)
        # left will be 1 element longer (keeps mid element), right does not

        # Even List:
        # curr = slow.next, (mid2.next)
        # left will be 2 elements longer (keeps mid1 and mid2), right does not

        curr = slow.next

        # Explicit Disconnect:
        # Set slow (belonging solely to left list)
        # to slow -> None
        slow.next = None 

        # Reverse second half of list
        while curr:
            # grab next
            next_node = curr.next
            # reverse flow
            curr.next = prev
            # iterate 
            prev = curr
            curr = next_node

        # iterate over left half and right half
        left, right = head, prev

        # Explicit Termination:
        # right half is always than the left half (by 1 or 2 nodes)
        # when we terminate right,
        # right.next = next_left guarantees that 
        # the rest of the left list was connected,
        # and since we already terminated the left list 'Explicit Disconnect'
        # our merged list will terminate
        while right:
            # grab next before disconnect
            next_left, next_right = left.next, right.next
            # alternate flow
            left.next = right
            right.next = next_left
            # iterate left and right half -> connect next_nodes
            left, right = next_left, next_right
        
        # overall: time complexity O(n)
        # overall: space complexity O(1)

    def reorderList(self, head: Optional[ListNode]) -> None:

        # Note
        # 1. Use Tortoise and Hare to find midpoint.
        # 2. Reverse the second half in place (without disconnecting manually)
        # 3. Merge first and reversed second half alternating nodes
        # Result: Fully in place reordering

        slow = fast = head
        while fast and fast.next:
            # slow travels half distance vs fast pointer: iterate references in memory
            fast = fast.next.next
            slow = slow.next
        
        # Slow result:
        # Odd List: slow -> odd mid
        # Even List: slow -> mid2

        # prev for reverse tail
        prev = None

        # Set Curr:

        # Odd List:
        # curr = slow, (mid)
        # left and right will be even (both keep mid element)

        # Even List:
        # curr = slow, (mid2)
        # left will be 1 element longer (keeps mid1 and mid2), (right keeps mid2)

        curr = slow

        # Implicit Disconnect:
        # Both left and right contain slow (either odd mid or mid2) in their list
        # during the first modification of slow, we point it to prev (None)
        # now, both lists have a slow.next -> None

        # Reverse second half of list:
        while curr:
            # grab next before disconnect
            next_node = curr.next
            # reverse flow
            curr.next = prev
            # iterate reference in memory
            prev = curr
            curr = next_node

        # iterate over left and right lists
        left, right = head, prev

        # Implicit Termination:
        # Now since:
        # left equal or longer by 1,
        # slow -> None is contained by both lists,
        # we will reach right's copy of slow
        # at the same time or earlier by 1 iteration.
        # However, when we reach right's copy,
        # right.next = next_left guarantees that
        # the rest of the left list was connected,
        # and since we already terminated the left list 'Implicit Disconnect'
        # our merged list will terminate
        while right != slow:
            next_left, next_right = left.next, right.next
            left.next = right
            right.next = next_left
            left, right = next_left, next_right

        # brain teaser:
        # why does this work:
        right.next = None
        # but right.next.next = None 
        # does not work

        # overall: time complexity O(n)
        # overall: space complexity O(1)

    def reorderList(self, head: Optional[ListNode]) -> None:

        # Note:
        # 1. Use Tortoise Hare to find the middle
        # 2. Iterate over right half in order and store elements in stack
        # 3. Pop all elements (in reverse order) and place in between left elements:
        # left -> right -> left.next
        # Result: Fully reordered

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

        # Slow result:
        # Odd List: slow -> odd mid
        # Even List: slow -> mid2
        
        # store right half list in order
        # space complexity: store half list of n length O(n)
        stack = []

        # Set Curr:

        # Odd List:
        # curr = slow.next, (mid.next)
        # left will be 1 element longer (keeps mid element), right does not

        # Even List:
        # curr = slow.next, (mid2.next)
        # left will be 2 elements longer (keeps mid1 and mid2), right does not

        curr = slow.next 

        # Explicit Disconnect:
        # Set slow (belonging solely to left list)
        # to slow -> None      
        slow.next = None  

        # time complexity: iterate over list of n length O(n)
        while curr:
            stack.append(curr)
            curr = curr.next

        # forward iteration over list 
        left = head

        # Odd List Len: left will be 1 element longer (keeps mid element)
        # Even List Len: left is 2 elements longer (keeps 1st and 2nd mid elements)

        # Explicit Termination:
        # right half stack is always than the left half (by 1 or 2 nodes)
        # when we terminate right,
        # right.next = next_left guarantees that 
        # the rest of the left list was connected,
        # and since we already terminated the left list 'Explicit Disconnect'
        # our merged list will terminate
        # time complexity: iterate over stack O(n)
        while stack:

            # iterate over right half
            right = stack.pop()

            # set: left -> right -> left.next 
            right.next = left.next
            left.next = right

            # iterate left list
            left = right.next

        # overall: time complexity O(n)
        # overall: space complexity O(n)

    def reorderList(self, head: Optional[ListNode]) -> None:

        # Note:
        # 1. Use Tortoise Hare to find the middle
        # 2. Iterate over right half in order and store elements in stack
        # 3. Pop all elements (in reverse order) and place in between left elements:
        # left -> right -> left.next
        # Result: Fully reordered

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

        # Slow result:
        # Odd List: slow -> odd mid
        # Even List: slow -> mid2

        # store right half list in order
        # space complexity: store list of n length O(n)
        stack = []

        # Set Curr:

        # Odd List:
        # curr = slow, (mid)
        # left and right will be even (both keep mid element)

        # Even List:
        # curr = slow, (mid2)
        # left will be 1 element longer (keeps mid1 and mid2), (right keeps mid2)
    
        curr = slow 

        # No Implicit Disconnect:
        # (deal with that later)
        
        # time complexity: iterate over list of n length O(n)
        while curr:
            stack.append(curr)
            curr = curr.next

        # iterate over left list 
        left = head

        # time complexity: iterate over stack O(n)
        while stack:

            # grab right half node element
            right = stack.pop()

            # place right half node in between left half curr and curr.next: 
            # curr -> tail -> curr.next 
            right.next = left.next
            left.next = right

            # iterate left half of list
            left = right.next

        # brain teaser:
        # why does this work:
        # Odd/Even Case:
        # left is equal or longer by 1 node
        # Odd: 
        # left and right are equal in length, both share 'slow'
        # so at the last iteration, left -> right -> left.next
        # but we never disconnected, so left slow -> right slow
        # and since they share the same object in memory
        # this does not matter since it is pointing to itself
        # Even:
        # left is longer by 1, both share 'slow'
        # last iteration, right slow -> left slow
        # but we never disconnected, so left slow -> right slow
        # and since they share the same object in memory
        # this does not matter since it is pointing to itself
        right.next.next.next.next.next = None

        # overall: time complexity O(n)
        # overall: space complexity O(n)

    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        
        # Note:
        # 1. Traverse list once to calculate total length
        # 2. Use a dummy node to handle edge cases (like removing head)
        # 3. Traverse again, stop at node prior to removal index
        # 4. point prior.next = prior.next.next, disconnecting removal node
        # Result: removed node at distance n from end of list

        # First pass: get length of list
        listLen = 0
        curr = head
        while curr:
            listLen += 1
            curr = curr.next

        # Second pass: find the node behind target index

        remove = listLen - n

        # we adding an element to the list
        dummy = ListNode(0, head)
        curr = dummy

        # this stops at the Node before the target remove index
        # thus we can disconnect it
        index = 0
        while index != remove:
            index += 1
            curr = curr.next
        
        # remove nth node from end by skipping it
        curr.next = curr.next.next

        # Return head dummy is pointing to (may be different from original)

        # overall: time complexity O(n)
        # overall: space complexity O(1)
        return dummy.next

    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        
        # Note:
        # 1. Use two pointers spaced n+1 apart (fast and slow)
        # 2. Move both pointers until fast hits end
        # 3. Slow pointer will be right before the node to remove
        # 4. Remove node by skipping it
       
        dummy = ListNode(-1, head)
        slow = fast = dummy
        
        # Set fast pointer: 
        # head start of n + 1 step,
        # in order to create a gap of n between fast and slow
        # (taking dummy node into account)
        index = 0
        while index != n+1:
            index += 1
            fast = fast.next
        
        # When fast reaches end:
        # n + 1 gap between slow (within list) and fast (end of list)
        while fast:
            fast = fast.next
            slow = slow.next
        
        # skip nth node
        slow.next = slow.next.next

        # Return head dummy is pointing to (may be different from original)

        # overall: time complexity O(n)
        # overall: space complexity O(1)
        return dummy.next 

    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        
        # Note:
        # .get() returns 'None' if nothing exists,
        # so perfect for our use case

        # Note:
        # 1. Traverse once: create all nodes (no wiring of next/random yet)
        # 2. Use a dictionary to map old nodes -> new nodes
        # 3. Traverse Twice: wire up both next and random using the map
        # 4. Return deep copy of head

        # Empty Check
        if not head:
            return None

        # Orig node -> deep node copy
        orig_to_deepCopy = {}

        # Iteration 1: 
        # Copy all nodes values (no next/random pointers yet)
        curr = head
        while curr:
            # create
            copy = Node(curr.val)
            # insert
            orig_to_deepCopy[curr] = copy
            # iterate
            curr = curr.next

        # Iteration 2:
        # All nodes created, now assign next and random pointers
        curr = head
        while curr:
            # grab curr deepCopy
            copy = orig_to_deepCopy[curr]
            # grab and set next and random deepCopy (value could be None, .get() returns None by default if no answer exists)
            copy.next = orig_to_deepCopy.get(curr.next)
            copy.random = orig_to_deepCopy.get(curr.random)
            # iterate
            curr = curr.next

        # Return deep copy of the head node

        # overall: time complexity O(n)
        # overall: space complexity O(n)
        return orig_to_deepCopy[head]

    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        
        # Note:
        # 1. Maintain a memo dictionary to store mapping on the fly
        # 2. Iterate once through original list while building the copy
        # 3. Create each copy node only whe first encountered (lazy construction)
        # 4. Maintain a pointer to build out the next chain

        # Empty check
        if not head:
            return None
        
        # dummy node head trick
        dummy = Node(-1)

        # prev allows deepCopy to connect once we create them lazily
        # for the entire deepCopy list as we go
        prev = dummy
        curr = head

        # orig -> deepCopy
        memo = {}
        
        # time complexity: iterate over list of n length
        while curr:
            
            # grab or create and grab curr deepCopy
            if curr not in memo:
                memo[curr] = Node(curr.val)
            currDeepCopy = memo[curr]
            
            # validate curr.random
            if curr.random:
                # grab or create and grab curr.random deepCopy
                if curr.random not in memo:
                    memo[curr.random] = Node(curr.random.val)
                currDeepCopy.random = memo[curr.random]
            
            # First iteration: dummy points to deepCopy head
            # next iteration: previous deepCopy node points to current deepCopy node 
            # after termination: entire deepCopy list is now connected
            prev.next = currDeepCopy

            # iterate to current deepCopy node connect next node
            # iterate over original list
            prev = prev.next
            curr = curr.next
        
        # Return deepCopy head
        
        # overall: time complexity O(n)
        # overall: space complexity O(n)

        return memo[head]
        # or
        # return dummy.next

    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        
        # Note:
        # 1. First interleave copy and paste nodes between original nodes O(1) space
        #    A -> B -> C ===> A -> A' -> B -> B' -> C -> C'
        
        # 2. Assign random pointers to the copy nodes using original's .random

        # 3. Detach copy list from original (restoring original list) 
        #    and setting valid .next for deepCopy list
        #    A -> A' -> B -> B' -> C -> C' ===> A' -> B' -> C'
        
        # 4. Return deepCopy head
        # Result: constant space within original list, but requires 3 passes 
        
        # Empty Check
        if not head:
            return None

        # Interleave deepCopy nodes
        # A -> A' -> B -> B' -> C -> C'
        curr = head
        while curr:
            # create and interweave
            deepCopy = Node(curr.val)
            deepCopy.next = curr.next

            # link A -> A' and iterate to next orig
            curr.next = deepCopy
            curr = deepCopy.next

        # Assign random pointers
        curr = head
        while curr:
            # grab intertwined deepCopy
            deepCopy = curr.next

            # assign random from orig if non None
            if curr.random:
                deepCopy.random = curr.random.next

            # iterate to next orig
            curr = deepCopy.next

        # Split orig and deepCopy list
        # (A) orig head: A -> A' -> B -> ...
        curr = head
        # (A') deepCopy head: A -> A' -> B -> ...
        deepCopyHead = head.next

        # time complexity: iterate over list of 2n length O(n)
        while curr:
            # grab deepCopy
            deepCopy = curr.next
            
            # link orig to next orig node, iterate to next orig
            # A -> A' -> B -> ...
            # A -> B
            curr.next = deepCopy.next
            curr = curr.next

            # if new orig is non None 
            # (B' -> C -> ...) vs (B' -> None)
            # there will exists a new deepCopy
            # iterate to deepCopy
            if curr:
                deepCopy.next = curr.next

        # return deepCopy head

        # overall: time complexity O(n)
        # overall: space complexity O(1)
        return deepCopyHead

    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        
        # Note:
        # 1. Recursion to simulate digit addition with carry
        # 2. Add Corresponding digits with carry passed to recursive call
        # 3. Current node created with .next -> recursively created node
        # 4. Base case: both lists empty and carry is 0
        # Result: new sum list created recursively
        
        # time complexity: iterate over two lists of m and n length O(max(m, n))
        # space complexity: recursive call over two lists of m and n length O(max(m, n))
        def recursiveSum(l1, l2, carry):
            
            # Base Case:
            # Both lists and carry are empty
            if not l1 and not l2 and carry == 0:
                return None

            # grab values if exist
            val1 = l1.val if l1 else 0
            val2 = l2.val if l2 else 0

            # sum
            sum = val1 + val2 + carry
            carry = sum//10

            # iterate lists if exist
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None

            # new node and attach
            newNode = ListNode(sum % 10)
            newNode.next = recursiveSum(l1, l2, carry)

            # return: curr node -> rest of list
            return newNode

        # calculate new sum list over two lists

        # overall: time complexity O(max(m, n))
        # overall: space complexity O(max(m, n))
        return recursiveSum(l1, l2, 0)

    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        
        # Note:
        # 1. Dummy node to create a sum list
        # 2. Iterate over both lists until complete
        # 3. Added values node by node, and pass the carry
        # Result: sum of two lists

        # dummy trick to return curr head
        dummy = ListNode(-1)
        prev = dummy
        carry = 0

        # Traverse while either list or carry is non empty
        while l1 or l2 or carry:
            
            # grab if value exists
            v1 = l1.val if l1 else 0
            v2 = l2.val if l2 else 0

            # add values and carry
            sum = v1 + v2 + carry
            carry = sum // 10

            # create new Node for new value  
            newNode = ListNode(sum % 10)
            prev.next = newNode
            prev = prev.next

            # iterate list
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None


        # return new head of sum list

        # overall: time complexity O(max(m, n))
        # overall: space complexity O(1)
        return dummy.next

    def findDuplicate(self, nums: List[int]) -> int:

        slow = nums[0]
        fast = nums[0]

        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break

        slow = nums[0]

        # INCORRECT:
        # we are taking a step before the while loop check
        # (which in some edge cases will get messy)
        # Instead:
        # while True:
        #    if slow == fast:
        #        break
        #    slow = nums[slow]
        #    fast = nums[fast]
        while True:
            slow = nums[slow]
            fast = nums[fast]
            if slow == fast:
                break

        return slow

    def findDuplicate(self, nums: List[int]) -> int:
        
        # Note:
        # 1. Idea: Compare bit counts between full nums list and range [1..n]
        # 2. Duplicate number will cause extra set bits in some positions
        # 3. Identify bits where counts mismatch, reconstruct duplicate from bits

        n = len(nums) - 1
        bit_reconstruction = 0

        # max_bits = how many binary bits needed to represent the largest number
        # determines how many bit positions we need to check
        # [1, 3, 4, 2, 2] -> 4 bit_length is 3 bits (100 binary) 
        # we will check bit positions 0, 1, 2
        max_bit = max(num.bit_length() for num in nums)

        # building duplicate number by iterating over each available bit position
        # bit = 0 -> mask = 1 (binary 001)
        # bit = 1 -> mask = 2 (binary 010)
        # bit = 2 -> mask = 3 (binary 100)
        for bit in range(max_bit):

            # current mask
            # 0 -> 1 << 0 = 0001
            # 1 -> 1 << 1 = 0010
            # 2 -> 1 << 2 = 0100
            # 3 -> 1 << 3 = 1000
            mask = 1 << bit

            # for each num in array, count if bit is set
            # &: bitwise AND
            # sets current bit to 1 if both mask and bit are set to 1
            # else sets current bit to 0,
            # determines if current num has the bit set
            curr_bit_set_count = sum((num & mask) > 0 for num in nums)

            # across expected range [1..n], sum if bit is expected to be set
            # &: bitwise AND
            # checks how many numbers within range [1..n]
            # are expected to have current bit set.
            expected_bit_set_count = sum((i & mask) > 0 for i in range(1, n + 1))

            # compare bit set to expected bit set,
            # if bit is set more times than expected
            # duplicate number must have that bit set:
            # add it to bit reconstruction
            if curr_bit_set_count > expected_bit_set_count:
                bit_reconstruction |= mask
        
        # overall: time complexity O(n log n)
        # overall: space complexity O(1)
        return bit_reconstruction

    def findDuplicate(self, nums: List[int]) -> int:

        # Note:
        # Idea: Duplicate number must satisfy pigeonhole principle:
        #   With n+1 numbers range [1..n], at least one value is duplicated
        #  (n containers, n+1 pigeons -> at least one container has two pigeons)
        
        # 1. Binary search on value range [1..n]
        # 2. For mid value:
        #    mid = number of containers in lower half (including mid)
        #    count = numbers of pigeons (nums <= mid) in lower half
        # 3. Decision:
        #   If count <= mid -> equal or lesser pigeons to containers -> duplicate is in upper half
        #   Else count > mid -> more pigeons than containers -> duplicate is in lower half

        # smallest value 1
        # largest value n (but we have n+1) n+1 - 1 -> n (the largest value)
        left, right = 1, len(nums) - 1

        # [ 1 4 3 5 2 ], for some n,
        # there must be n-1 numbers below:
        # for 2, there is 1 number below
        # for 5, there are 4 numbers below
        # Binary optimization search: '<'
        while left < right:
            
            mid = (left + right) // 2

            # count how many numbers <= mid
            curr_count = sum(num <= mid for num in nums)

            # if count <= mid, there are no extra numbers in lower half:
            # duplicate must be in upper half
            if curr_count <= mid:
                left = mid + 1

            # if count > mid, there are too many numbers in lower half:
            # duplicate must be in lower half
            else:
                right = mid

        # Loop exit: left == right
        # left and right are pointing at duplicate number

        # overall: time complexity O(n log n)
        # overall: space complexity O(1)
        return left

    def findDuplicate(self, nums: List[int]) -> int:

        # Note:
        # 1. definitions
        # L = distance from head to start of cycle
        # C = length of the cycle (number of nodes in the cycle)
        # x = distance from the start of the cycle to the meeting point inside the cycle
        # k = number of full cycles the fast pointer has completed by the time of the first meeting

        # 2. setup
        # When slow and fast pointers first meet inside the cycle:
        
        # Slow pointer has traveled: L + x steps:
        #    L steps to reach the start of the cycle
        #    x steps inside the cycle to the meeting pointer

        # Fast pointer has traveled L + x + (k * C) steps:
        #    L steps to reach the start of the cycle
        #    x steps inside the cycle to the meeting point
        #    k full extra loops around the cycle (each length C)

        # Fast Substitute:
        # By definition, fast pointer speed is double slow pointer, so substitute
        #     L + x + (k * C) = 2(L + x)
        
        # Solve for L:
        #     L + x + kC = 2L + 2x
        #     kX = L + x
        #     L = kC - x 

        # Rewrite Rule Context:
        # Traveling x steps inside cycle of length C =
        # to traveling C - x steps backwards, due to wrap around
        # x steps forward = C - x backwards

        # 3. Rearrange
        #    L = kC - x
        #    L = kC + (C - x)

        #    L = kC + (C - x)   <-- this proves moving slow to right will cover

        # once we move slow to the head:
        # L -> distance from head to start of cycle

        # fast will stay at the meeting point:
        # kC + (C - x)

        # kC -> number of cycles (we can ignore this)
        # (C - x) -> steps remaining to get to the start (since we have traveled x steps already)

        # L = (C - x)
        # so both slow and fast will travel the same amount of steps 
        # to get to the start of the cycle


        # The above math proves the below algorithm:

        # Note:
        # Idea: Treat array as linked list: index -> nums[index]
        #    Problem set up with duplicate guarantees cycle in linked list representation
        
        # 1. Detect cycle (slow = nums[slow], fast = nums[nums[fast]])
        # 2. Move slow to head, advance both one step at a time to find cycle start (duplicate)

        # Find meeting point in cycle
        slow = nums[0]
        fast = nums[0]
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break

        # Move slow to head, move fast and slow one step at time,
        # fast and slow will meet at start of cycle
        slow = nums[0]
        while True:
            if slow == fast:
                break
            slow = nums[slow]
            fast = nums[fast]

        # overall: time complexity O(n)
        # overall: space complexity O(1)
        return slow

class Node:
    def __init__(self, key : int, val : int):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity : int):
        self.capacity = capacity
        self.cache = {}
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove_node(self, node:Node):
        prev, next = node.prev, node.next
        prev.next = next
        next.prev = prev

    def _push_MRU(self, node:Node):
        twoMRU = self.head.next
        node.next = twoMRU
        node.prev = self.head
        self.head.next = node
        twoMRU.prev = node

    def get(self, key:int):
        if key not in self.cache:
            return -1

        node = self.cache[key]
        self._remove_node(node)
        self._push_MRU(node)
        return node.val

    def put(self, key:int, val:int):
        if key in self.cache:
            node = self.cache[key]
            self._remove_node(node)
            node.val = val
        else:

            # INCORRECT:
            # forgot to add new node to cache
            # Instead:
            # node = self.cache[key] = node
            node = Node(key, val)

        self._push_MRU(node)

        if len(self.cache) > self.capacity:
            lruNode = self.tail.prev
            self._remove_node(lruNode)
            self.cache.pop(lruNode.key)

class Node:
    def __init__(self, key: int, val: int):

        # key -> value node
        self.key = key
        self.val = val
        # doubly linked prev and next
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity: int):

        # list capacity
        self.capacity = capacity

        # key -> Node
        self.cache = {} 

        # MRU head
        self.head = Node(0, 0)
        # LRU tail
        self.tail = Node(0, 0)

        # set dummy head and tail
        self.head.next = self.tail
        self.tail.prev = self.head

    # time complexity: O(1)
    # space complexity: O(1)
    def _remove_node(self, node: Node):

        # Remove node from doubly linked list by linked neighbors
        prev, next = node.prev, node.next
        prev.next = next
        next.prev = prev

    # time complexity: O(1)
    # space complexity: O(1)
    def _push_MRU(self, node: Node):

        # Insert node between dummy head and MRU 
        node.next = self.head.next
        node.prev = self.head

        # Update head and 2nd MRU
        self.head.next = node
        node.next.prev = node

    # time complexity: O(1)
    # space complexity: O(1)
    def get(self, key: int) -> int:       

        # if node does not exist, return -1
        if key not in self.cache:
            return -1

        # grab node
        node = self.cache[key]

        # Move node and update MRU
        self._remove_node(node)
        self._push_MRU(node)

        # return val
        return node.val

    # time complexity: O(1)
    # space complexity: O(1)
    def put(self, key: int, value: int) -> None:

        # If key exists, remove to avoid duplicates,
        # need to grab node to update prev and next nodes
        if key in self.cache:
            node = self.cache[key]
            self._remove_node(node)

            # update existing node
            node.val = value

        # If key does not exist, create new node set to new value
        else:
            node = Node(key, value)
            self.cache[key] = node

        # push updates node to top of MRU
        self._push_MRU(node)

        # Remove LRU if capacity broken
        if len(self.cache) > self.capacity:
            lruNode = self.tail.prev
            self._remove_node(lruNode)
            self.cache.pop(lruNode.key)

    # overall: time complexity O(1)
    # overall: space complexity O(1)

class LRUCache:
    def __init__(self, capacity: int):
        
        # OrderedDict in Python is implemented internally
        # as a doubly linked list + hashmap (same as our solution):
        self.cache = OrderedDict()
        self.capacity = capacity

    # time complexity: O(1) 
    # space complexity: O(1)
    def get(self, key: int) -> int:

        # Check if key exists, else return -1
        if key not in self.cache:
            return -1

        # Update MRU
        self.cache.move_to_end(key)

        # return value
        return self.cache[key]

    # time complexity: O(1)
    # space complexity: O(1)
    def put(self, key: int, value: int) -> None:

        # If key exists, remove to avoid duplicates
        if key in self.cache:
            self.cache.pop(key)
        
        # Insert new value, automatically updates MRU,
        # automatically updates doubly linked list
        self.cache[key] = value
        
        # capacity exceeded, remove LRU
        if len(self.cache) > self.capacity:
            
            # last=True -> pops MRU
            # last=False -> pops LRU
            self.cache.popitem(last=False)

    # overall: time complexity O(1)
    # overall: space complexity O(1)

    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        
        # Note:
        # 1. minHeap stores current head for each sorted list
        # 2. minHeap sorted by value, list_index breaking ties: 
        #    (value, list_index, node)
        # 3. smallest value across heads added to list
        # 4. push to minHeap to replaced added node
        # Result: merge list in O(n log k)

        # minHeap of: (val, list index, node)
        min_heap = []

        # Push the head of each non-empty list into the heap
        for i_list, head_list in enumerate(lists):
            if head_list:
                # minHeap sorted by node.val,
                # i_list index used to break ties
                heappush(min_heap, (head_list.val, i_list, head_list))  

        dummy = ListNode(-1)
        prev = dummy

        # Pop smallest node, attach to merged list, push from same list if min.next
        while min_heap:

            # grab min value
            minVal, i_list, node = heappop(min_heap)
            prev.next = node
            prev = prev.next

            # valid node.next for current i_list
            if node.next:
                # grab next node from i_list
                heappush(min_heap, (node.next.val, i_list, node.next))

        # minHeap empty -> all lists empty
        # return head of merged list

        # overall: time complexity O(n log k)
        # overall: space complexity O(k)
        return dummy.next

    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        
        # Note:
        # 1. Merge lists in pairs with standard merge two sorted lists
        # 2. Each round halves the total number of lists -> O(log k) rounds
        # 3. Each round processes all nodes (across all merges) -> O(n) work per round
        # Result: Merging k lists in place
        
        # Empty check
        if not lists: 
            return None

        # Merge two sorted linked lists
        # time complexity: iterate over lists of n length O(n)
        def mergeTwo(l1, l2):

            # dummy node trick
            dummy = ListNode(-1)
            prev = dummy

            # merge while both lists non empty
            while l1 and l2:
                # grab smaller head
                if l1.val < l2.val:
                    prev.next = l1
                    l1 = l1.next
                else:
                    prev.next = l2
                    l2 = l2.next
                # iterate
                prev = prev.next

            # attach remaining list 
            if not l1:
                prev.next = l2 
            else:
                prev.next = l1

            # return merged new merged list
            return dummy.next

        # iteratively merge lists in pairs until one list remains
        # time complexity: log(len(list)) total merges
        while len(lists) > 1:
            merged = []
            for i in range(0, len(lists), 2):
                l1 = lists[i]
                l2 = lists[i + 1] if i + 1 < len(lists) else None
                merged.append(mergeTwo(l1, l2))
            lists = merged

        # overall: time complexity O(n log k)
        # overall: space complexity O(1)
        return lists[0]

    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        
        # Note:
        # 1. Check if there are at least k nodes ahead (otherwise return head)
        # 2. Reverse the first k nodes
        # 3. Recurse and process sub list
        # 4. Connect reversed head with resulting sub list
        # Result: original lists with reversed groups of k length

        # Base case: check if at least k nodes remain
        kLen = 0
        node = head
        while node and kLen < k:
            kLen += 1
            node = node.next

        # Base case: less than k nodes, return head
        if kLen < k:
            return head  

        # ----
        # standard reverse linked list

        # Reverse current sub list up to k
        prev = None
        curr = head
        for _ in range(k):
            # grab next
            next = curr.next
            # reverse flow
            curr.next = prev
            # iterate
            prev = curr
            curr = next
        
        # curr -> start of next sub list
        # prev -> new head of curr sub list
        # head -> new tail of curr sub list
        # connect head (new tail) via head.next to next reversed sub list
        head.next = self.reverseKGroup(curr, k)
        
        # return prev (new head) of curr sub list
        
        # overall: time complexity O(n)
        # overall: space complexity O(n/k) ~ O(n) recursive stack
        return prev

    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        
        # Note:
        # 1. Dummy node handles head swaps cleanly
        # 2. For each sub list:
        #    Find the kth node
        #    Reverse the group in place
        #    Connect previous reverse group's tail to head of new reversed group
        # 3. Continue until remaining nodes < k, then return

        # dummy node trick for head of overall list
        dummy = ListNode(0, head)

        # group_prev_tail points to tail of the previous reverse group,
        # where group.next points to head of next list
        group_prev_tail = dummy

        # while remaining sub list is greater than k
        while True:

            # last item in previous reversed sub list
            kth_elem = group_prev_tail
            # check if k more elements exist
            for _ in range(k):
                kth_elem = kth_elem.next

                # less than k nodes remain, return head of entire list
                if not kth_elem:
                    return dummy.next 

            # next sub list start
            group_next = kth_elem.next

            # ----
            # standard reverse linked list

            # Reverse group [group_prev_tail.next, kth]
            prev = group_next
            curr = group_prev_tail.next

            # Reverse group in place for nodes [0, k):
            for _ in range(k):
                # grab next
                next = curr.next
                # reverse flow
                curr.next = prev
                # iterate
                prev = curr
                curr = next

            # group_prev_tail -> (new tail) of prev sub list
            # curr -> head of next sub list
            # prev -> (new head) of curr sub list
            # group_prev_tail.next -> (new tail) of curr sub list

            # ----
            # connect new tail of previous sub list 
            # to new head of curr sub list

            # last node of previous group, still pointing to original head,
            # which is now the tail 
            curr_tail = group_prev_tail.next
            
            # point last node of previous group, to new head of curr sub list
            group_prev_tail.next = prev
            # update last node of previous group, to last node of curr sub list
            group_prev_tail = curr_tail

        # overall: time complexity O(n)
        # overall: space complexity O(1)