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, currNode: Optional[ListNode]) -> Optional[ListNode]:
        
        # Recursive Linked Lists:
        # A linked list is made up of nodes which point to other nodes
        # They must have pointers and they may or may not have values:
        #
        #   () -> () -> () -> None
        #   (1) -> (3) -> (7) -> None

        # Reverse Linked List:
        #   - Update parents to point to their children
        #   - Original head points to None (becoming a tail)
        #   - Return the original tail representing the start of the list (becoming a head)
        #
        #           (1) -> (3) -> (7) -> None
        #   None <- (1) <- (3) <- (7)


        # Empty Case:
        #   - Nothing to reverse, just return 'None'
        if currNode == None:
            return currNode

        # Base Case: 
        #   - Reached 'None' of original list
        #   - CurrHead is at the original tail, which will become the new head, 
        #   - Begin passing original tail back up the recursive call
        # tc: O(1)
        if currNode.next == None:
            return currNode

        # Recursion: 
        # call reverse list on the rest of the list (head.next to end), 
        # and eventually the base case starts to pass back the tail (new head)
        # Recursive call stack is n times so O(n) space and time
        # tc: O(n)
        # sc: O(n)
        newHead = self.reverseList(currNode.next)


        # -----------------
        # Reverse order next and curr node
        
        # Point next node to current node 
        currNode.next.next = currNode

        # Point curr node to 'None' (temporarily act as a tail)
        currNode.next = None

        # overall: tc O(n)
        # overall: sc O(n)
        return newHead

    def reverseList(self, currNode: Optional[ListNode]) -> Optional[ListNode]:

        # Reverse Linked List:
        #   - Update parents to point to their children
        #   - Original head points to None (becoming a tail)
        #   - Return the original tail representing the start of the list (becoming a head)
        #   (1) -> (3) -> (7) -> None
        #   None <- (1) <- (3) <- (7)

        # See Solution 1 Notes:
        # Same as previous, just simplified with 'not'
        # In python 'None' is considered 'falsy', 
        # meaning it behaves like False in conditional statements such as this one
        
        # Empty Case:
        #   - Nothing to reverse, just return 'None'
        if not currNode:
            return currNode

        # Base Case: 
        #   - Reached 'None' of original list
        #   - CurrHead is at the original tail, which will become the new head, 
        #   - Begin passing original tail back up the recursive call
        # tc: O(1)
        if not currNode.next:
            return currNode

        # reverse the rest of the list (.next onwards)
        newHead = self.reverseList(currNode.next)
        
        next = currNode.next
        next.next = currNode

        currNode.next = None

        # overall: tc O(n)
        # overall: sc O(n)
        return newHead 

    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        
        # Reverse Linked List:
        #   - Update parents to point to their children
        #   - Original head points to None (becoming a tail)
        #   - Return the original tail representing the start of the list (becoming a head)
        #   (1) -> (3) -> (7) -> None
        #   None <- (1) <- (3) <- (7)

        # Creating a 'None' to act as the end of the list,
        # so the new tail can point at it
        prev = None

        # Curr will point to the previous element
        curr = head

        # Iterate until we have reached the end of the list 
        # (remember the tail points to None):
        #   head -> () -> () -> tail -> None
        # tc: iterate over n O(n)
        while curr != None:

            # Grab next node before disconnecting from current node
            nextNode = curr.next  

            # Reverse/disconnect current element, 
            # and point to previous node: 
            curr.next = prev      

            # Before reverse:
            #      <- prev    curr -> next -> ()

            # After reverse:
            #      <- prev <- curr    next -> ()

            # Iterate both nodes: prev and curr
            prev = curr
            curr = nextNode

            # Before iteration:
            #     <- prev <- curr    next -> ()

            # After iteration:
            #     <- ()   <- prev    curr -> ()
     

        # Loop exits when curr == None:
        
        # Before exiting:
        #       () -> tail -> None

        # After exiting:
        #       () <- prev -> curr

        # curr is at 'None'
        # prev is at the original tail / the new head
        newHead = prev

        # overall: tc O(n)
        # overall: sc O(1)
        return newHead  

    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        
        # Reverse Linked List:
        #   - Update parents to point to their children
        #   - Original head points to None (becoming a tail)
        #   - Return the original tail representing the start of the list (becoming a head)
        #   (1) -> (3) -> (7) -> None
        #   None <- (1) <- (3) <- (7)

        prev = None
        curr = head

        # See Solution 3 Notes:
        # Same as previous, just simplified with 'not'
        # In python 'None' is considered 'falsy', 
        # meaning it behaves like False in conditional statements such as this one
        while curr:

            nextNode = curr.next  

            curr.next = prev      

            prev = curr            
            curr = nextNode       

        # overall: tc O(n)
        # overall: sc O(1)
        return prev  

    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:

        # Merge Linked Lists: 
        #   - Compare two current heads of lists, grab smaller one
        #   - Iterate the head we just grabbed
        #   - When one list runs out of items, link the rest of the non empty list

        
        # List1 and List2:
        #   (1) -> (3) -> (7) -> None
        #   (2) -> (9) -> (10) -> None

        # MergedList:
        #   (1) -> (2) -> (3) -> (7) -> (9) -> (10) -> None
      
        # Base case: 
        # One of the lists is empty, 
        # return remaining portion of the non empty list up the recursion call
        if not list1:
            return list2
        if not list2:
            return list1

        # Compare two current heads of lists, grab smaller one:
        if list1.val < list2.val:

            # Grab list1 node,
            # iterate the head we just grabbed by passing the next node to the recursive call,
            # and connect list1 node by pointing to the rest of the merged list
            list1.next = self.mergeTwoLists(list1.next, list2)
            
            # return merged list1 node
            return list1
        
        else:

            # Grab list2 node,
            # iterate the head we just grabbed by passing the next node to the recursive call,
            # and connect list2 node by pointing to the rest of the merged list
            list2.next = self.mergeTwoLists(list1, list2.next)

            # return merged list2 node
            return list2

        # overall: tc O(n + m)
        # overall: sc O(n)

    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        
        # Merge Linked Lists: 
        #   - Iterate over both lists at the same time
        #   - Compare two current heads of lists, grab smaller one
        #   - When one list runs out of items, link the rest of the non empty list
        
        # List1 and List2:
        #   (1) -> (3) -> (7) -> None
        #   (2) -> (9) -> (10) -> None

        # MergedList:
        #   (1) -> (2) -> (3) -> (7) -> (9) -> (10) -> None

        # DummyHead:
        #   - Allows entering the iterative loop cleanly
        #     without handling first node assigning case
        #   - Always points at original head
        # sc: O(1)
        dummyHead = ListNode(-1)

        # Linked List Iterator:
        # sc: O(1)
        curr = dummyHead

        # Traverse both lists while both have nodes
        # tc: O(m + n)
        while list1 and list2:

            # grab smaller value between the two and iterate that list
            if list1.val < list2.val:

                # Grab list1 node
                # iterate list1 (new head becomes next node) 
                curr.next = list1
                list1 = list1.next

            else:

                # Grab list2 node
                # iterate list2 (new head becomes next node) 
                curr.next = list2
                list2 = list2.next    

            # iterate merged list
            curr = curr.next          

        # One list is empty,
        # connect remaining portion of non-empty list
        if list1:
            curr.next = list1
        else:
            curr.next = list2

        # Originally:
        #   dh      lst1 -> () -> ...
        #  curr     lst2 -> () -> ...

        # After:
        #   dh  ->  merged -> () -> ...

        # dummyHead:
        # dh is still pointing to original head of the merged list
        newHead = dummyHead.next

        # overall: tc O(m + n)
        # overall: sc O(1)
        return newHead

    def hasCycle(self, head: Optional[ListNode]) -> bool:
        
        # Linked List Cycles:
        #
        #   (1) -> (3) -> (7) -> (9)
        #                  ^      |     (cycle)
        #                  |      v
        #                 (11)<- (10)


        # Linked List Cycle Validation:
        # To check if a linked list, we simply iterate over the list
        # while keeping a set of nodes we have seen,
        # and if we try to add a node we have already seen, a cycle exists
        
        # Nodes stored by obj reference:
        # sc: O(n)
        seen = set()

        # Linked List Iteration Representation:
        # sc: O(1)
        curr = head

        # Iterate until we hit the 'None' at the end of the list
        # tc: iterate over list O(n)
        while curr:

            # Check: is current node in seen list
            # Implies: we have passed through as cycle
            if curr in seen:
                return True

            # Implies: have not seen current node
            # Then: add to seen list, continue iteration
            seen.add(curr)
            
            # Iterate
            curr = curr.next
        
        # Implies: have reached the end of list, no node was seen twice
        # Then: no cycles exist

        # overall: tc O(n)
        # overall: sc O(n)
        return False

    def hasCycle(self, head: Optional[ListNode]) -> bool:
        
        # Floyd Cycle Detection Algorithm (Tortoise And Hare):

        # Iterate linked list using 2 pointers:
        #   - fast: a pointer going 2x speed (hare)
        #   - slow: a pointer going 1x speed (tortoise)

        # Cycle Validation:
        #   - Cycle exists:
        #       fast pointer hit the cycle and catches up with slow
        #   - No cycle Exists:
        #       fast pointer exits linked list and never catches up
        #       with slow

        # Linked List Cycle:
        #
        #   (1) -> (3) -> (7) -> (9)
        #                  ^      |     (cycle)
        #                  |      v
        #                 (11)<- (10)


        # Floyd Iterators:
        # sc: O(1)
        slow, fast = head, head
        
        # Iterate until either:
        #   - fast hits the 'None' at the end of the list
        #   - fast hits the slow pointer
        # tc: iterate over n O(n) 
        while fast and fast.next:

            # Iterate slow 1x and fast 2x
            slow = slow.next
            fast = fast.next.next
            
            # Check: if fast hit slow
            # Implies: fast passed through a cycle
            if slow == fast:
                return True

        # Implies: fast has reached end of list, 
        #          never caught up with slow, no cycle exists in list
        
        # overall: tc O(n)
        # overall: sc O(1)
        return False

    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:

        # ----------------------------------------------------------------------------------
        # Linked List Find Cycle Start Algorithm Proof:

        # 1. Variable 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:
        #   Iteration 1: Slow + Fast Until They Meet
        #   Slow Reset:  After Slow + Fast Meet, 
        #                immediately set Slow back to head,
        #                then run again until Slow and Fast meet again
        #   Iteration 2: After the reset, 
        #                Slow and Fast are guaranteed to meet at the cycle start
        
        # -----------------------------------------
        # Solving For L Variable Definitions: 
        
        #   Distance Traveled:
        #           L + x + (k * C) steps
        #   Where:
        #           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)

        # Solving For L:

        #   Total Distance Traveled To Meeting Point:

        #     Distance = Distance
        #     Fast Pointer Distance = Slow Pointer Distance
        #     L + x + (k * C)       = 2(L + x)
        
        # Solve for L:
        #     L + x + kC = 2L + 2x
        #             kX = L + x
        #              L = kC - x 

        # -----------------------------------------
        # Cycle Wrap around Proof
        # Traveling x steps inside cycle of length C =
        # to traveling C - x steps backwards, due to wrap around
        # x steps forward = C - x backwards
        # so:
        #   x = C - x

        # -----------------------------------------
        # Plugging In L Variable Definition and Wrap Around Proof: 
        
        #    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


        # -----------------------------------------
        # Treating The Array Like A Linked List With A Cycle:

        # Cycle:
        # since the list only has 1 duplicate (which may appear multiple times), 
        # that means a cycle exists.

        # Array: value: [3, 1, 3, 4, 2]
        #        index:  0  1  2  3  4


        # Treat array as linked list: index -> nums[index]
        #    Problem set up with duplicate guarantees cycle in linked list representation
        
        # Array (Linked List) With Cycle (Horizontal):
        #
        #       value:   3        4        2        3        4        2
        #       index:  [0]  ->  [3]  ->  [4]  ->  [2]  ->  [3]  ->  [4] ...
        
        # Array (Linked List) With Cycle (Vertical + Horizontal):
        #
        # value:   3        4        2        3   
        # index:  [0]  ->  [3]  ->  [4]  ->  [2] 
        #                   ^                 ^
        #                   |                 |
        #                   -------------------
        #                         cycle

        # nums[0]=3  ->  jump to index 3
        # nums[3]=4  ->  jump to index 4
        # nums[4]=2  ->  jump to index 2
        # nums[2]=3  ->  jump to index 3   <= We've been here already,
        #                                     We've hit index 3 twice, cycle!
        
        # Per this diagram:
        #           The goal is then to find the start of the cycle,
        #           which starts at the duplicate number,
        #           in this case the duplicate value of 3 at index 0 and 2
        #           with the start of the cycle being at index 3


        # ----------------------------------------------------------------------------------
        # The 3 Step Modified Floyd Cycle Algorithm

        # -----------------------------------------
        # Iteration 1:

        # Ran Slow and Fast normally at x1 and x2 respectively, 
        # until they meet somewhere in the linked list

        # Slow Pointer:
        #   Distance Traveled:
        #           L + x steps
        #   Where:
        #           L steps to reach the start of the cycle
        #           x steps inside the cycle to the meeting pointer


        # -----------------------------------------
        # Iteration 1: First Meeting Point

        # Linked List Iterators:
        # sc: O(1)
        slow = nums[0]
        fast = nums[0]

        # Iterate Slow and Fast at x1 and x2 respectively so they meet at: 
        
        #        Slow                       Fast
        #     L + x + (k * C) steps      = 2(L + x) steps

        # steps into the cycle where:
        #   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)        
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break

        # -----------------------------------------
        # Reset Slow: Set Back To Head

        # Reset slow to head to prepare for iteration 2
        slow = nums[0]


        # -----------------------------------------
        # Iteration 2: Second Meeting Point

        # Fast and slow will meet at start of cycle, 
        # which starts at some instance of the duplicate number
        # (duplicate number may appear more than twice)
        while True:
            if slow == fast:
                break
            slow = nums[slow]
            fast = nums[fast]

        # overall: tc O(n)
        # overall: sc O(1)
        return slow

    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        
        # Note:
        # 1. List is already sorted, so duplicates are always adjacent
        # 2. Walk the list, whenever curr.val == curr.next.val, skip curr.next
        # 3. Otherwise advance curr
        # No dummy node needed since we never remove the head

        curr = head

        while curr and curr.next:
            if curr.val == curr.next.val:
                # skip duplicate
                curr.next = curr.next.next
            else:
                # no duplicate, advance
                curr = curr.next

        return head

        # tc: O(n)
        # sc: O(1)

    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        
        # Note:
        # 1. Dummy node needed since head itself may be a duplicate
        # 2. prev pointer trails behind, only advances when curr group is distinct
        # 3. When we find a duplicate value, skip ALL nodes with that value
        # 4. Otherwise, advance prev and curr normally

        dummyHead = ListNode(0, head)
        prev = dummyHead
        curr = head

        while curr:
            # check if curr is start of a duplicate group
            if curr.next and curr.val == curr.next.val:
                # skip all nodes with this value
                dupVal = curr.val
                while curr and curr.val == dupVal:
                    curr = curr.next
                # connect prev to first node after duplicate group
                prev.next = curr
            else:
                # distinct node, safe to advance prev
                prev = curr
                curr = curr.next

        return dummyHead.next

        # tc: O(n)
        # sc: O(1)

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

        # -----------------------------------------
        # Linked List Reorder Pattern:

        # Before
        #   (1) -> (2) -> (3) -> (4) -> (5) -> None

        # After
        #   (1) -> (5) -> (2) -> (4) -> (3) -> None

        # This combination is a zig zag of the following:
        # (1 connects to 5, then 2, then 4, etc)
        #
        # list1 =>   (1) -> (2) -> (3) -> None
        # list2 =>      (5) -> (4) -> None     (+)

        # Where:
        # list1 = first half of the list
        # list2 = reversed second half of the list

        # -----------------------------------------
        # 1. First Half Of List 
        #   - keep pointing to original head
        #   - stop iteration at half
        #   - point middle to None to split list in half

        # -----------------------------------------
        # 2. Reversed Second Half Of List
        #   - stop iteration at half
        #   - keep pointing at middle element
        #   - reverse list starting at middle element

        # -----------------------------------------
        # 3. Join the two elements
        #   - iterate over forward and reversed list
        #   - add in correct order 
 

        # -----------------------------------------
        # 1. First Half Of List

        # Floyd Cycle Algorithm Variation:
        #   - use the slow fast pointers to find the middle of the list

        # Odd Even Case:
        #   - depending on whether the list has an even or odd number of nodes,
        #     slow pointer will stop at either:
        #
        #                  s            f
        #      () -> () -> () -> () -> () -> None
        #                 mid
        #
        #                  s     f
        #      () -> () -> () -> () -> None
        #           mid1  mid2

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

        # Slow result:
        # Odd List:  
        #   - slow = mid
        # Even List: 
        #   - slow = mid2

        # -----------------------------------------
        # Prepare for 2. reverse list:
        #   1.1: set curr to beginning of right half
        #   1.2: disconnect left and right half of lists

        # Odd List: 
        #   - curr = slow.next, (mid.next)
        #     left will be 1 element longer (keeps mid element)
        #
        #    - - - - L - - -     - - R - - 
        #                  s   s.next  f
        #      () -> () -> () -> () -> () -> None
        #                 mid

        # Even List:
        #   - curr = slow.next, (mid2.next)
        #     left half will be 2 elements longer (keeps mid1 and mid2)
        #
        #    - - - - L - - -    - R -
        #                      s.next 
        #                  s      f
        #      () -> () -> () -> () -> None
        #           mid1  mid2

        # Prepare for iterative reversal with prev/curr
        prev = None
        curr = slow.next

        # Disconnect 1st half of list:
        # Set slow to be the tail of the left list (belonging solely to left list)
        #   - slow -> None
        slow.next = None 

        # Odd Even Case:
        #                  s      s.next  f
        #      () -> () -> ()       () -> () -> None
        #                 mid
        #                  | 
        #                  V
        #                 None
        # 
        #                         s.next 
        #                  s         f
        #      () -> () -> ()       () -> None
        #           mid1  mid2
        #                  |
        #                  v
        #                 None


        # -----------------------------------------
        # 2. Reverse Second Half Of List

        # Keep reversing until we reach the end of the right half
        # tc: O(n/2) ~ O(n) 
        while curr:

            # grab next and reverse flow
            next_node = curr.next
            curr.next = prev
            
            # iterate 
            prev = curr
            curr = next_node

        # After iteration:
        # prev = tail
        # prev.next = None


        # -----------------------------------------
        # 3. Connect First Half And Reversed Second Half:

        # iterate over left half and right half
        #   - head is still at the start of the original list (start of the left half)
        #   - prev is at the end of the original list (start of the right half) 
        left = head
        right = prev

        # Explicit Termination Needed:
        # right half is always shorter than the left half 
        # (by 1 or 2 nodes for even and odd original lists, see above)
        # These extra 1 or 2 nodes serve as a prepared tail for the left half: 

        #    - - - - L - - -      - - R - - 
        #                  s             f
        #   (1) -> (2) -> (3) -> (4) -> (5)        (1) -> (2) -> (3) -> None       (1) -> (5) -> (2) -> (4) -> (3) -> None
        #                 mid                 ==>     (5) -> (4) -> None      ==> 
        #                                                        ^
        #                                                      right terminates,
        #                                                      notice how "(3) -> None" is already prepared
        #    - - - - L - - -    - R -                           
        #                  s      f          
        #   (1) -> (2) -> (3) -> (4)               (1) -> (2) -> (3) -> None       (1) -> (4) -> (2) -> (3) -> None
        #           mid1  mid2                ==>      (4) -> None            ==> 
        #                                                  ^
        #                                                 right terminates,
        #                                                 notice how "(2) -> (3) -> None" is already prepared

        # The extra 1 or 2 prepared tail, 
        # allows us to know that when right terminates,
        # the rest of the remaining list is already in the correct order
        while right:

            # grab next before disconnect
            next_left, next_right = left.next, right.next

            # merge lists with the alternating pattern (see above)
            left.next = right
            right.next = next_left

            # iterate both lists 
            left, right = next_left, next_right
        

        # overall: tc O(n)
        # overall: sc O(1)

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

        # -----------------------------------------
        # Linked List Reorder Pattern:

        # Before
        #   (1) -> (2) -> (3) -> (4) -> (5) -> None

        # After
        #   (1) -> (5) -> (2) -> (4) -> (3) -> None

        # This combination is a zig zag of the following:
        # (1 connects to 5, then 2, then 4, etc)
        #
        # list1 =>   (1) -> (2) -> (3) -> None
        # list2 =>      (5) -> (4) -> None     (+)

        # Where:
        # list1 = first half of the list
        # list2 = reversed second half of the list


        # -----------------------------------------
        # 1. First Half Of List 
        #   - keep pointing to original head
        #   - stop iteration at half
        #   - point middle to None to split list in half

        # -----------------------------------------
        # 2. Reversed Second Half Of List
        #   - stop iteration at half
        #   - keep pointing at middle element
        #   - reverse list starting at middle element

        # -----------------------------------------
        # 3. Join the two elements
        #   - iterate over forward and reversed list
        #   - add in correct order 

    
        # -----------------------------------------
        # 1. First Half Of List

        # Floyd Cycle Algorithm Variation:
        #   - use the slow fast pointers to find the middle of the list

        # Odd Even Case:
        #   - depending on whether the list has an even or odd number of nodes,
        #     slow pointer will stop at either:
        #
        #                  s            f
        #      () -> () -> () -> () -> () -> None
        #                 mid
        #
        #                  s     f
        #      () -> () -> () -> () -> None
        #           mid1  mid2
 
        # slow travels half distance vs fast pointer
        slow = fast = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
 
        # Slow result:
        # Odd List:  
        #   - slow = mid
        # Even List: 
        #   - slow = mid2

        # -----------------------------------------
        # Prepare for 2. reverse list:
        #   1.1: set curr to beginning of right half
        #   1.2: disconnect left and right half of lists

        # Odd List: 
        #   - curr = slow, (mid)
        #     left will be 1 element longer (keeps mid element)
        #
        #    - - - - L - - -     - - R - - 
        #                  s           f
        #      () -> () -> () -> () -> () -> None
        #                 mid

        # Even List:
        #   - curr = slow, (mid2)
        #     left and right half will be equal
        #
        #     - - L - -    - - R - -                        
        #                  s      f
        #      () -> () -> () -> () -> None
        #           mid1  mid2


        # Prepare for iterative reversal with prev/curr
        prev = None
        curr = slow

        # Implicit Disconnect:
        # Both left and right contain slow (either odd mid or mid2) in their list
        # during the first iteration of reversing the list, we set "slow -> None"
        # now, both lists share the same reference to  "slow -> None"

        # Odd Even Case:
        #   - depending on whether the list has an even or odd number of nodes,
        #     slow pointer will stop at either:
        #
        #                  s              f
        #      () -> () -> ()       () -> () -> None
        #                 mid
        #                  |
        #                  V
        #                 None
        #
        # 
        #                  s         f
        #      () -> () -> ()        () -> None
        #           mid1  mid2
        #                  |
        #                  V
        #                 None


        # Implicit Right -> Left Connect:
        # In the first iteration of the reversal we set "slow -> None" and then "slow.next -> slow":
        #
        #                  s             f
        #      () -> () -> ()   <- () -> () -> None
        #                 mid
        #                  |
        #                  V
        #                 None
        #
        # 
        #                  s        f
        #      () -> () -> ()   <-  () -> None
        #           mid1  mid2
        #                  |
        #                  V
        #                 None

        # -----------------------------------------
        # 2. Reverse Second Half Of List

        # Keep reversing until we reach the end of the right half
        # tc: O(n/2) ~ O(n) 
        while curr:

            # grab next and reverse flow
            next_node = curr.next
            curr.next = prev

            # iterate 
            prev = curr
            curr = next_node

        # After iteration:
        # prev = tail
        # prev.next = None


        # -----------------------------------------
        # 3. Connect First Half And Reversed Second Half:

        # iterate over left half and right half
        #   - head is still at the start of the original list (start of the left half)
        #   - prev is at the end of the original list (start of the right half)
        left = head
        right = prev

        # Implicit Termination:
        # right is either equal or shorter than the left half
        # (by 1 node for odd and equal length for even original lists, see above)
        # This extra 1 node or evenness serve as a prepared tail for the left half

        #    - - - - L - - -     - - R - - 
        #                  s             f
        #   (1) -> (2) -> (3) -> (4) -> (5)       (1) -> (2) -> (3) -> None       (1) -> (5) -> (2) -> (4) -> (3) -> None
        #                 mid                ==>     (5) -> (4) -> (mid/3)      ==> 
        #                                                        ^
        #                                                      right terminates,
        #                                                      notice how "(4) -> (3) -> None" is already prepared
        #
        #    - - L - -     - - R - -                           
        #                  s      f          
        #   (1) -> (2) -> (3) -> (4)               (1) -> (2) -> (3) -> None       (1) -> (4) -> (2) -> (3) -> None
        #           mid1  mid2                ==>      (4) -> (5) -> (mid/3)            ==> 
        #                                                          ^
        #                                                        right terminates,
        #                                                        notice how "(4) -> (3) -> None" is already prepared

        # the extra 1 or even tail,
        # allows us to know that when right == slow,
        # the rest of the remaining list is already in the correct order
        # tc: O(n/2) ~ O(n) 
        while right != slow:

            # grab next before disconnect
            next_left, next_right = left.next, right.next

            # merge lists with the alternating pattern (see above)
            left.next = right
            right.next = next_left

            # iterate both lists 
            left, right = next_left, next_right

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

        # overall: tc O(n)
        # overall: sc 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 reorderList(self, head: Optional[ListNode]) -> None:

        holder

    def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # Note:
        # 1. Dummy node needed since sorted portion grows from scratch
        # 2. curr walks the unsorted input list one node at a time
        # 3. For each curr, walk the sorted list from dummy to find insertion point
        # 4. Insert curr between prev and prev.next in sorted list

        dummyHead = ListNode(0)
        curr = head

        while curr:
            # save next unsorted node before we overwrite curr.next
            nextUnsorted = curr.next

            # find insertion point in sorted list:
            # walk until prev.next is >= curr, or end of sorted list
            prev = dummyHead
            while prev.next and prev.next.val < curr.val:
                prev = prev.next

            # insert curr between prev and prev.next
            curr.next = prev.next
            prev.next = curr

            # advance to next unsorted node
            curr = nextUnsorted

        return dummyHead.next

        # tc: O(n^2)  — for each node, walk sorted portion to find insertion point
        # sc: O(1)

    def insertionSortList(self, head: ListNode | None) -> ListNode | None:
        dummy = ListNode(0)
        prev = dummy  # the last and thus largest of the sorted list

        while head:  # the current inserting node
            next = head.next  # Cache the next inserting node.
            if prev.val >= head.val:
                prev = dummy  # Move `prev` to the front.
            while prev.next and prev.next.val < head.val:
                prev = prev.next
            head.next = prev.next
            prev.next = head
            head = next  # Update the current inserting node.

        return dummy.next

    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # Note:
        # 1. Find midpoint with slow/fast pointers, split list in two
        # 2. Recurse on each half
        # 3. Merge the two sorted halves
        # Base case: 0 or 1 nodes, already sorted

        # base case
        if not head or not head.next:
            return head

        # find midpoint and split
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # split: slow is end of left half
        mid = slow.next
        slow.next = None

        # recurse on each half
        left = self.sortList(head)
        right = self.sortList(mid)

        # merge sorted halves
        dummy = ListNode(0)
        curr = dummy
        while left and right:
            if left.val <= right.val:
                curr.next = left
                left = left.next
            else:
                curr.next = right
                right = right.next
            curr = curr.next
        curr.next = left or right

        return dummy.next

        # tc: O(n log n) — log n splits, O(n) merge per level
        # sc: O(log n)   — recursion stack depth

    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # Note:
        # 1. Count list length
        # 2. Instead of recursing top-down, merge bottom-up
        # 3. Start with sublist size=1, merge pairs, double size each round
        # 4. log n rounds, O(n) work per round -> O(n log n), O(1) space

        if not head or not head.next:
            return head

        # count length
        length = 0
        node = head
        while node:
            length += 1
            node = node.next

        dummy = ListNode(0, head)

        size = 1
        while size < length:
            curr = dummy.next
            tail = dummy       # tail of last merged group

            while curr:
                # split off left half of size `size`
                left = curr
                right = split(left, size)
                curr  = split(right, size)

                # merge left and right, attach to tail
                merged, tail = merge(left, right)
                tail.next = curr   # connect to remainder

            size *= 2

        return dummy.next

        # tc: O(n log n)
        # sc: O(1)


    def split(head, size):
        # walk `size` steps, sever link, return new head
        for _ in range(size - 1):
            if not head:
                return None
            head = head.next
        if not head:
            return None
        rest = head.next
        head.next = None
        return rest


    def merge(l1, l2):
        # merge two sorted lists, return (head, tail)
        dummy = ListNode(0)
        curr = dummy
        while l1 and l2:
            if l1.val <= l2.val:
                curr.next = l1
                l1 = l1.next
            else:
                curr.next = l2
                l2 = l2.next
            curr = curr.next
        curr.next = l1 or l2
        while curr.next:
            curr = curr.next
        return dummy.next, curr

        # tc: O(n)
        # sc: O(1)

    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # Note:
        # 1. Maintain two sublists: odd-indexed and even-indexed
        # 2. odd  pointer weaves through nodes 1, 3, 5, ...
        # 3. even pointer weaves through nodes 2, 4, 6, ...
        # 4. Save even head, append even list to end of odd list

        if not head:
            return head

        odd  = head
        even = head.next
        evenHead = even

        while even and even.next:
            # advance odd to next odd node
            odd.next  = even.next
            odd       = odd.next
            # advance even to next even node
            even.next = odd.next
            even      = even.next

        # attach even list to end of odd list
        odd.next = evenHead

        return head

        # tc: O(n)
        # sc: O(1)

    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 total length of list
        # tc: O(n)
        listLen = 0
        curr = head
        while curr:
            listLen += 1
            curr = curr.next

        # DummyHead to keep track of original head
        # sc: O(1)
        dummyHead = ListNode(-1, head)

        # Linked List Iterator
        # sc: O(1)
        curr = dummyHead

        # Second Pass: calculate distance to node behind the target node
        removeDist = listLen - n
        i = 0
        while i != removeDist:
            i += 1
            curr = curr.next
        
        # Arrived at n-1th node:
        # simply skip the nth node
        curr.next = curr.next.next

        # Originally:
        #   dh  ->  lst1 -> () -> ...
        #  curr     

        # After
        #   dh  ->   ()  -> () -> ...

        # overall: tc O(n)
        # overall: sc O(1)
        return dummyHead.next

    def removeNthFromEnd(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        
        # Note:
        # 1. Use two pointers spaced nth 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
       
        # DummyHead to keep track of original head
        # sc: O(1)
        dummyHead = ListNode(-1, head)
        
        # Linked List Iterators
        # sc: O(1)
        slow = fast = dummyHead
        
        # Modified Floyd Algorithm With Fast Stopping:
        # instead of doing fast x2 iteration, 
        # do a x1 iteration and make it stop at k+1 instead of 'None'
        # tc: O(n)
        i = 0
        while i != k+1:
            i += 1
            fast = fast.next

        # Fast is now at the nth index
        # [ slow ... fast ... None]
        #   0    ...  k   ...  n

        # Modified Floyd Algorithm With Fast Starting At k:        
        # There is a distance of k between the slow and fast pointers
        # [slow .... n + 1 .... fast]
        
        # Iterate slow and fast until fast reaches end of list:
        # tc: O(n)
        while fast:
            fast = fast.next
            slow = slow.next

        # Before Iteration:
        # slow = head
        # fast = skip.next

        # After Iteration:
        # slow = skip.prev
        # fast = 'None'
        
        # Slow is pointing to Node we are planning to skip:
        # skip it by changing .next to its parent (.next.next)
        slow.next = slow.next.next

        # Originally:
        #   dh  ->  lst1 -> () -> ...
        #  curr     

        # After
        #   dh  ->   ()  -> () -> ...

        # overall: tc O(n)
        # overall: sc O(1)
        return dummyHead.next