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

Sol 2: Iterative Reversal Using Prev and Curr:
1. (prev = None)
2. (curr = head)
3. while curr != None:
    a. nextNode = curr.next
    b. curr.next = prev
    c. prev = curr
    d. curr = nextNode
4. newHead = prev
5. return newHead

    def reverseList(self, currNode: Optional[ListNode]) -> Optional[ListNode]:
        
        # Recursive Reversal:
        #   - Recurse down to the original tail, which becomes the new head
        #   - As the call stack unwinds, each node's next pointer is flipped to point backward
        #   - The original head ends up with next = None, becoming the new tail

        # Reversal Phase:

        # Input:              (1) -> (3) -> (7) -> None

        # Recurse down:       (1) -> (3) -> (7) -> None
        # to original tail                   ^ 
        #                                base case: newHead = (7)

        # Unwind:             (1) -> (3) <- (7)
        #     (flip 7,3)                newHead still (7)

        # Unwind:             (1) <- (3) <- (7)
        #     (flip 3,1)       ^ currNode.next = None (new tail)

        # Final:      None <- (1) <- (3) <- (7)

        # Note:
        # 1. Base case: currNode is None or currNode.next is None, already at new head
        # 2. Recurse first, then reverse the link on the way back up
        # 3. currNode.next.next = currNode flips the pointer direction
        # 4. currNode.next = None severs the old forward link

        # Empty List:
        # Nothing to reverse
        if currNode == None:
            return currNode

        # Base Case:
        # Reached the original tail, 
        # becomes the new head by being passed back
        if currNode.next == None:
            return currNode

        # Recurse to the end of the list before reversing any links
        # to hit the base case above
        # tc: O(n)
        # sc: O(n) — recursion stack depth
        newHead = self.reverseList(currNode.next)

        # Unwinding:
        # Reverse the link between curr and next node
        currNode.next.next = currNode

        # Sever the old forward link, curr temporarily acts as a tail
        currNode.next = None

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

    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        
        # Iterative Reversal:
        #   - prev trails behind curr, holding the already reversed portion of the list
        #   - Each node's next pointer is flipped to point at prev before advancing
        #   - Once curr runs off the end, prev is left at the new head

        # Reversal Phase:

        # Input:    None    (1) -> (3) -> (7) -> None
        #            ^       ^
        #           prev    curr

        # Step 1:   None <- (1)    (3) -> (7) -> None
        #                    ^      ^
        #                   prev   curr

        # Step 2:   None <- (1) <- (3)    (7) -> None
        #                           ^      ^
        #                          prev   curr

        # Step 3:   None <- (1) <- (3) <- (7)    None (loop exits)
        #                                  ^      ^
        #                                 prev   curr

        # Note:
        # 1. prev starts at None, will end up as the new head
        # 2. curr walks the original list, one node at a time
        # 3. Save nextNode before overwriting curr.next, or the rest of the list is lost
        # 4. Loop exits when curr == None, prev holds the new head

        # Prev acts as the new tail, will end up as the new head
        prev = None

        # Curr acts as the node we are reversing
        curr = head

        # tc: O(n)
        while curr != None:

            # Grab next node before severing connection
            nextNode = curr.next

            # Flip connection, reversing node
            curr.next = prev

            # Advance to flip next node
            prev = curr
            curr = nextNode

        # Curr is at None
        # Prev is at the original tail which is now the new head
        newHead = prev

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

Sol 1: Pairwise Swap:
1. dummy = ListNode(0, head)
2. prev = dummy
3. while prev.next and prev.next.next:
    a. first = prev.next
    b. second = prev.next.next
    c. first.next = second.next
    d. second.next = first
    e. prev.next = second
    f. prev = first
4. return dummy.next

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

        # Pairwise Swap:
        #   - Adjacent nodes are swapped two at a time
        #   - Each swapped pair is stitched back to the node before it
        #   - A dummy node is used since the head itself may be swapped away

        # Swapping Phase:

        # Input:    1 -> 2 -> 3 -> 4 -> null
        #      dummy -> 1

        # Step 1:   dummy -> 2 -> 1 -> 3 -> 4 -> null
        #                         prev

        # Step 2:   dummy -> 2 -> 1 -> 4 -> 3 -> null
        #                                   prev

        # Idea:
        #   - Keep a dummy node before head so the first pair can be swapped uniformly
        #   - prev always points to the node just before the current pair
        #   - For each pair: grab first/second, rewire their next pointers, reconnect prev,
        #     then advance prev to the end of the swapped pair (old first node)

        # Note:
        # 1. Dummy node needed since head itself gets swapped
        # 2. prev trails behind, stitches each swapped pair back to the list
        # 3. For each pair: save pointers, swap, reconnect, advance

        dummyHead = ListNode(0, head)
        curr = curr

        # Swap each adjacent pair, two nodes at a time
        # tc: O(n)
        while curr.next and curr.next.next:

            # Grab the current pair to swap
            pairOne = curr.next
            pairTwo = curr.next.next


            # curr -> first -> second -> third -> fourth

            # Move first to skip second, and now point to third
            first.next = second.next

            # Reverse flow for second, point second to first
            second.next = first

            # Move curr to skip first, and now point to second
            curr.next = second

            # Advance curr to the node before the pair of third and fourth
            curr = first

        # Grab head of new list
        newHead = dummyHead.next

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

Sol 1: Recursive:
1. kLen = 0, node = head
2. while node and kLen < k:
    a. kLen = kLen + 1
    b. node = node.next
3. if kLen < k:
    a. return head
4. prev = null, curr = head
5. for i in range(k):
    a. next = curr.next
    b. curr.next = prev
    c. prev = curr
    d. curr = next
6. head.next = reverseKGroup(curr, k)
7. sectionNewHead = prev
8. return sectionNewHead

Sol 2: Iterative:
1. dummyHead = ListNode(0, head)
2. somePrevTail = dummyHead
3. while true:
    a. kthNode = somePrevTail
    b. for i in range(k):
        - kthNode = kthNode.next
        - if not kthNode: return dummyHead.next
    c. nextHead = kthNode.next
    d. prev = nextHead
    e. curr = somePrevTail.next
    f. for i in range(k):
        - next = curr.next
        - curr.next = prev
        - prev = curr
        - curr = next
    g. currTail = somePrevTail.next
    h. somePrevTail.next = prev
    i. somePrevTail = currTail

    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        
        # ------------------------------------------------
        # Reverse Nodes In k-Group Pattern: State 
        
        #   k = 3, input: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> None
        #
        #   Before:
        #   [1] -> [2] -> [3] -> [4] -> [5] -> [6] -> None

        #   After:
        #   [2] -> [1] -> [4] -> [3] -> [6] -> [5] -> None

        # 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

        # Early Exit:
        # Get length of list,
        # if list has less than k nodes, return head        
        kLen = 0
        node = head
        while node and kLen < k:
            kLen += 1
            node = node.next
        if kLen < k:
            return head  


        # Standard Iterative Linked List Reversal:

        # Linked List Iterators:
        # sc: O(1)
        prev = None
        curr = head

        # Reverse the first k nodes
        # tc: O(k)
        for _ in range(k):
            
            # Grab next node before disconnecting
            # from current node
            next = curr.next

            # reverse flow of current node
            curr.next = prev
            
            # Iterate Linked List
            prev = curr
            curr = next
        
        # Head is still pointing to original first node,
        # but this original first node is now the new tail,
        # which needs to be connected to the head of the 
        # next section, hence: we need to update head.next
        head.next = self.reverseKGroup(curr, k)
        
        # Prev is pointing to the original tail of the k section,
        # but this original tail becomes the new head,
        # hence, we need to return it up the recursive call
        sectionNewHead = prev

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

    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        
        # ------------------------------------------------
        # Reverse Nodes In k-Group Pattern: State 
        
        #   k = 3, input: 1->2->3->4->5->6->None
        #
        #   Before:
        #   [1] -> [2] -> [3] -> [4] -> [5] -> [6] -> None

        #   After:
        #   [2] -> [1] -> [4] -> [3] -> [6] -> [5] -> None

        # 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

        # --------------------------------
        # Initial State: k = 3, input: 1->2->3->4->5->6->None
        #
        #   [dummy] -> [1] -> [2] -> [3] -> [4] -> [5] -> [6] -> None
        #      |
        #   somePrevTail

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

        # Iterate linked list, while we still have at least k nodes
        # tc: O(n)
        while True:

            # ------------------------------------------------
            # Check if k nodes remain

            # Last node (tail) of the prev k section
            kthNode = somePrevTail

            # Early Exit:
            # If remaining list has less than k nodes, return head
            # check if k more elements exist
            for _ in range(k):

                # Check next node
                kthNode = kthNode.next
                if not kthNode:
                    # return head
                    return dummyHead.next 

            # Reverse the next k section of nodes: 
            nextHead = kthNode.next

            # Linked List Iterators:
            # sc: O(1)
            prev = nextHead
            curr = somePrevTail.next

            # --------------------------------
            # After walking k steps, 
            # saving next section head, 
            # initializing curr/prev:
            #
            #                  curr                 prev
            #                   |                    |
            #   [dummyHead] -> [1] -> [2] -> [3] -> [4] -> [5] -> [6] -> None
            #        |                        |      |
            #    somePrevTail               kthNode  nextHead


            # ------------------------------------------------
            # Standard Iterative Linked List Reversal:

            # Reverse k nodes:
            for _ in range(k):
                
                # Grab next node before disconnecting from current node
                next = curr.next

                # Reverse curr node, point to previous node
                curr.next = prev

                # Iterate linked list
                prev = curr
                curr = next

            # After reversal:
            #   
            #      - - - - - - - - - - - - - - 
            #      |           prev           |     curr
            #      |            |             v      |
            #   [dummyHead]    [3] -> [2] -> [1] -> [4] -> [5] -> [6] -> None
            #      |                          ^
            #   groupPrevTail               (groupPrevTail.next,
            #   (unchanged)                  original head, now tail
            #                               of reversed group)
            #
            #                  - - - - - - - - -      - - - - - - - -
            #                   prev k section         curr k section
            #
            #
            # Connecting prev/curr sections:
            #   - groupPrevTail:       tail of the *previous* k section (dummy here on iter 1)
            #   - groupPrevTail.next:  original head / new tail of the group we just reversed
            #   - prev:                original tail / new head of the group we just reversed
            #   - curr:                head of the *next* k section (not yet reversed)

            # To link the "prev" and curr" sections: we need to:
            #   - connect the new tail of the previous k section => to the new head of the curr k section 

            # Grab head of the *next* k section (not yet reversed),
            # grab [4] in the above diagram
            currTail = somePrevTail.next
            
            # Grab dummyHead to point to new head,
            # [3] in this case
            somePrevTail.next = prev
            # update last node of previous group, to last node of curr sub list
            somePrevTail = currTail

            # After adjusting links:
            #   
            #              prev                 curr
            #               |                    |
            #   [dummy] -> [3] -> [2] -> [1] -> [4] -> [5] -> [6] -> None
            #      |                      ^
            #   groupPrevTail           (groupPrevTail.next,
            #   (unchanged)              original head, now tail
            #                            of reversed group)
            #
            #              - - - - - - - - -      - - - - - - - -
            #               prev k section         curr k section

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

Sol 2: Iterative Merging Compare Node At Each And DummyHead Trick:
1. dummyHead = ListNode(-1)
2. curr = dummyHead
3. while list1 and list2:
    a. if list1.val < list2.val:
        curr.next = list1
        list1 = list1.next
    b. else:
        curr.next = list2
        list2 = list2.next
    c. curr = curr.next
4. if list1:
    curr.next = list1
5. else:
    curr.next = list2
6. newHead = dummyHead.next
7. return newHead

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

        # Recursive Merge:
        #   - At each level, the smaller of the two current heads is chosen
        #   - That node's next pointer is wired to the result of merging the rest of the list
        #   - Recursion bottoms out once one list is exhausted

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

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

        # Compare heads of both lists, grab smaller one:
        # tc: O(n + m)
        # sc: O(n + m) — recursion stack depth
        if list1.val < list2.val:

            # Grab list1 node:
            # recurse on its remainder against list2
            list1.next = self.mergeTwoLists(list1.next, list2)
            
            # return merged list1 node
            return list1
        
        else:

            # Grab list2 node:
            # recurse on its remainder against list1
            list2.next = self.mergeTwoLists(list1, list2.next)

            # return merged list2 node
            return list2

        # overall: tc O(n + m) — each node visited once across recursion
        # overall: sc O(n + m) — recursion stack depth

    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        
        # Iterative Merge:
        #   - Both lists are walked simultaneously, one pointer each
        #   - The smaller of the two current nodes is appended to the merged list each step
        #   - Once one list is exhausted, the remainder of the other is attached directly
        
        # list1:    (1) -> (3) -> (7) -> None
        # list2:    (2) -> (9) -> (10) -> None

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

        # DummyHead:
        #   - Allows entering the iterative loop cleanly without handling first node assigning case
        #   - Points to the new head
        dummyHead = ListNode(-1)

        # Iterator:
        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:
                curr.next = list1
                list1 = list1.next

            else:
                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

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

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

Sol 2: Iterative Digit by Digit Addition:
1. dummy = ListNode(-1)
2. prev = dummy
3. carry = 0
4. while l1 or l2 or carry:
    a. v1 = l1.val if l1 else 0
    b. v2 = l2.val if l2 else 0
    c. sum = v1 + v2 + carry
    d. carry = sum // 10
    e. newNode = ListNode(sum % 10)
    f. prev.next = newNode
    g. prev = prev.next
    h. l1 = l1.next if l1 else null
    i. l2 = l2.next if l2 else null
5. return dummy.next

    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:
            # Stop once we have nothing to add
            #   - Both lists are empty
            #   - We have no carry
            if not l1 and not l2 and carry == 0:
                return None

            # Check if value exists and grab
            val1 = l1.val if l1 else 0
            val2 = l2.val if l2 else 0

            # Check curr 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

            # Create new node and put curr sum into it
            newNode = ListNode(sum % 10)

            # Attach node to next node
            newNode.next = recursiveSum(l1, l2, carry)

            # Pass curr node back up recursive calls
            # tc: O(n)
            # sc: O(n)
            return newNode

        # calculate new sum list over two lists

        # overall: tc O(max(m, n))
        # overall: sc 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

        # DummyHead to keep tack of original head
        dummy = ListNode(-1)
        prev = dummy

        # Tracking remainder
        remainder = 0

        # Traverse while we still have something to add
        #   - either list is non empty
        #   - we have a remainder value
        while l1 or l2 or remainder:
            
            # Check if value exists and grab
            v1 = l1.val if l1 else 0
            v2 = l2.val if l2 else 0

            # add values and remainder
            sum = v1 + v2 + remainder
            remainder = 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: tc O(max(m, n))
        # overall: sc O(n)
        return dummyHead.next

Sol 2: Floyd Cycle Detection Tortoise and Hare:
1. slow, fast = head, head
2. while fast and fast.next:
    a. slow = slow.next
    b. fast = fast.next.next
    c. if slow == fast:
        return True
3. return False

    def hasCycle(self, head: Optional[ListNode]) -> bool:
        
        # Seen-Set Detection:
        #   - Every visited node is recorded in a set
        #   - If a node is ever visited a second time, a cycle exists
        #   - If traversal reaches None, no node repeats and there is no cycle

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

        # Idea:
        #   - Walk the list one node at a time
        #   - Before advancing, check if curr has already been seen
        #   - If it has, we've looped back into a previously visited node: cycle found
        #   - Otherwise add curr to the seen set and continue

        # Note:
        # 1. Nodes are stored by object reference, not by value
        # 2. Reaching None means every node was visited exactly once, no cycle
        # 3. Revisiting a node before reaching None means a cycle exists
        
        # Nodes stored by obj reference:
        # sc: O(n)
        seen = set()

        # List Iterator:
        curr = head

        # tc: O(n)
        while curr:

            # Check: 
            # If node exists in seen list, we have pass through a cycle
            if curr in seen:
                return True

            # Add new node to seen list
            seen.add(curr)
            
            # Iterate
            curr = curr.next
        
        # Reached end if list:
        # No node was seen twice, no cycle exists

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

    def hasCycle(self, head: Optional[ListNode]) -> bool:
        
        # Floyd's Tortoise and Hare:
        #   - slow advances 1 step at a time, fast advances 2 steps at a time
        #   - If a cycle exists, fast eventually laps slow and they meet inside the cycle
        #   - If no cycle exists, fast reaches None before ever meeting slow

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

        # Idea:
        #   - Move slow one step and fast two steps each iteration
        #   - If fast ever equals slow, fast has lapped slow inside a cycle
        #   - If fast (or fast.next) hits None, the list ends and no cycle exists

        # Note:
        # 1. slow and fast both start at head
        # 2. Loop condition fast and fast.next guards against null-pointer access
        # 3. slow == fast mid-loop can only happen inside a cycle, never on a straight list

        # Floyd Iterators:
        slow = head
        fast = head
        
        # tc: O(n) 
        while fast and fast.next:

            # Iterate slow 1x and fast 2x
            slow = slow.next
            fast = fast.next.next
            
            # Check: 
            # Fast has caught with slow, fast passed through a cycle
            if slow == fast:
                return True
 
        # Fast reach end of list: 
        # Fast never caught up with slow, no cycle exists in list
        
        # overall: tc O(n)
        # overall: sc O(1)
        return False

Sol 3: 3 Step Floyd + Explicit Disconnect + In Place Reversal:
1. slow = fast = head
2. while fast and fast.next:
    a. slow = slow.next
    b. fast = fast.next.next
3. prev = null
4. curr = slow.next
5. slow.next = null
6. while curr:
    a. next_node = curr.next
    b. curr.next = prev
    c. prev = curr
    d. curr = next_node
7. left = head
8. right = prev
9. while right:
    a. next_left = left.next
    b. next_right = right.next
    c. left.next = right
    d. right.next = next_left
    e. left = next_left
    f. right = next_right

Sol 3: Floyd Cycle With Stack:
1. slow = fast = head
2. while fast and fast.next:
    a. slow = slow.next
    b. fast = fast.next.next
3. stack = []
4. curr = slow.next
5. slow.next = null
6. while curr:
    a. stack.append(curr)
    b. curr = curr.next
7. left = head
8. while stack:
    a. right = stack.pop()
    b. right.next = left.next
    c. left.next = right
    d. left = right.next

    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)
        return

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

        # Strategy:
        # 1. Use slow/fast pointers to find the middle
        # 2. Push the right half onto a stack (preserves order, reverses on pop)
        # 3. Pop each node and splice it in: left -> right -> left.next

        # Find Middle (Slow/Fast Pointers):
        # slow ends on mid for odd lists, mid2 for even lists
        # tc: O(n)
        slow = head
        fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # Set Curr:
        # curr = slow (NOT slow.next) -- includes the shared mid node
        # Odd List: left and right both include mid, so lengths are equal
        # Even List: left is 1 element longer (keeps mid1 and mid2), right keeps mid2 (shared)
        curr = slow

        # No Explicit Disconnect:
        # slow is never severed from the left half here (handled after merge)
        # (we exclude this -> slow.next = None)
        
        # Store Right Half:
        # sc: O(n/2) ~ O(n)
        # tc: O(n/2) ~ O(n)
        stack = []
        while curr:
            stack.append(curr)
            curr = curr.next

        # Merge Alternating:
        # left = original head (start of left half)
        # popping the stack yields right half nodes in reverse order
        left = head

        # Left Equal Or One Node Longer:
        # left and right share the mid node, so left is equal length (odd)
        # or one node longer (even) than right — no disconnect happens here,
        # so the list isn't yet terminated once the stack empties
        # tc: O(n)
        while stack:

            # Pop next right-half node (reverse order)
            right = stack.pop()

            # Splice right node in after left node
            right.next = left.next
            left.next = right

            # Advance left pointer
            left = right.next


        # brain teaser:
        # why does this work:
        # Both right and left shared the 'slow' node,
        # and in the last iteration, we set right.next = left.next
        # which means right is pointing to the shared 'slow' node,
        # which results in slow pointing to itself

        # 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: tc O(n)
        # overall: sc O(n)
        return

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

        # Reorder Pattern:
        # 1 -> 2 -> 3 -> 4 -> 5  becomes  1 -> 5 -> 2 -> 4 -> 3
        #
        # This is a zig-zag merge of:
        # list1 = first half:            1 -> 2 -> 3
        # list2 = reversed second half:  5 -> 4

        # Strategy:
        # 1. Find the middle and split the list into two halves
        # 2. Reverse the second half
        # 3. Merge the two halves by alternating nodes

        # -----------------------------------------
        # 1: Find Middle (Floyd Cycle Algorithm Slow/Fast Pointers)
        #   - slow travels half distance by the time fast makes it to the end
        #   - use the slow fast pointers to find the middle of the list
        #
        #   - slow ends on mid for odd lists
        #
        #                  s            f
        #      () -> () -> () -> () -> () -> None
        #                 mid
        #
        #   - slow mid2 for even lists
        #
        #                  s     f
        #      () -> () -> () -> () -> None
        #           mid1  mid2

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


        # -----------------------------------------
        # Prepare for 2. reverse list:
        #   - slow becomes tail of left list responsible for:
        #       a. creating head of right list
        #       b. sever left and right list

        # a) Create head of right list -> curr
        prev = None
        curr = slow.next

        # Odd lists:
        #   - slow ends on mid
        #   - left list will be 1 element longer (keeps mid)
        #   - s.next becomes head of right
        #
        #    - - - - L - - -     - - R - - 
        #                  s   s.next  f
        #      () -> () -> () -> () -> () -> None
        #                 mid

        # Even lists:
        #   - slow ends on mid2
        #   - left list will be 2 elements longer (keeps mid1 and mid2)
        #   - s.next becomes head of right
        #
        #    - - - - L - - -    - R -
        #                      s.next 
        #                  s      f
        #      () -> () -> () -> () -> None
        #           mid1  mid2


        # b) Sever left and right list
        slow.next = None 

        # Odd lists:
        #   - slow ends on mid for odd lists
        #
        #                  s      s.next  f
        #      () -> () -> ()       () -> () -> None
        #                 mid
        #                  | 
        #                  V
        #                 None

        # Even lists:
        #   - slow mid2 for even lists
        #
        #                         s.next 
        #                  s         f
        #      () -> () -> ()       () -> None
        #           mid1  mid2
        #                  |
        #                  v
        #                 None


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

        # Iterate reversal until we reach end of right half
        # tc: O(n/2) ~ O(n) 
        while curr:

            # Grab next node before severing connection
            nextNode = curr.next

            # Flip connection, reversing node
            curr.next = prev

            # Advance to flip next node
            prev = curr
            curr = nextNode

        # Curr is at None
        # Prev is at the original tail which is now the new head
        newRightHead = prev


        # -----------------------------------------
        # 3. Merge Left and Reversed Right List Alternating
        # - left = start of left half
        # - right = start of reversed right half
        left = head
        right = newRightHead

        # Right Half Always Shorter:
        #   - left half has 1-2 extra nodes (the middle element(s)),
        #   - once right is exhausted, the rest of the list is already in correct order
        #   - the 1-2 extra nodes on the left list acts as a prepared tail
        #   - the 1-2 prepared tails allows us to know when right terminates,
        #     the rest of the remaining list is already in the correct order

        # Prepared Tails:

        # Odd lists:
        #   - slow ends on mid for odd lists
        #
        #    - - - - 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
        
        # Even lists:
        #   - slow mid2 for even lists
        #
        #    - - - - 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

        # tc: O(n/2) ~ O(n) 
        while right:

            # Grab next before disconnect
            nextLeft = left.next
            nextRight = right.next

            # Merge lists alternating
            left.next = right
            right.next = nextLeft

            # Iterate both lists
            left = nextLeft
            right = nextRight

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

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

        # Reorder Pattern:
        # 1 -> 2 -> 3 -> 4 -> 5  becomes  1 -> 5 -> 2 -> 4 -> 3
        #
        # This is a zig-zag merge of:
        # list1 = first half:            1 -> 2 -> 3
        # list2 = reversed second half:  5 -> 4

        # Strategy:
        # 1. Find the middle and split the list into two halves
        # 2. Reverse the second half
        # 3. Merge the two halves by alternating nodes

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

        # Floyd Cycle Algorithm Variation:
        #   - slow travels half distance by the time fast makes it to the end
        #   - use the slow fast pointers to find the middle of the list
        #
        #   - slow ends on mid for odd lists
        #
        #                  s            f
        #      () -> () -> () -> () -> () -> None
        #                 mid
        #
        #   - slow mid2 for even lists
        #
        #                  s     f
        #      () -> () -> () -> () -> None
        #           mid1  mid2

        slow = head
        fast = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
 
        # -----------------------------------------
        # Prepare for 2. reverse list:
        #   - slow becomes tail of left list responsible for:
        #       a. creating head of right list
        #       b. sever left and right list

        # a) Create head of right list -> curr
        prev = None
        curr = slow

        # Odd List: 
        #   - slow ends on mid
        #   - left and right will be equal (share mid)
        #   - s stays tail of left
        #   - s becomes head of right
        #
        #    - - - - L - - -     - - R - - 
        #                  s           f
        #      () -> () -> () -> () -> () -> None
        #                 mid

        # Even List:
        #   - slow ends on mid2
        #   - left will be 1 element longer (share mid)
        #   - s stays tail of left
        #   - s becomes head of right
        #
        #     - - L - -    - - R - -                        
        #                  s      f
        #      () -> () -> () -> () -> None
        #           mid1  mid2


        # Implicit Disconnect:
        # - Left and right share slow in their list (odd mid or even mid2)
        # - during the right reversal, we set 'slow -> None'
        # - Will act as a prepared tail for the eventually merged list

        # Reversal First Iteration:
        #   - we set "slow -> None" 
        #   - we set "slow.next -> slow":
        #
        #                  s             f
        #      () -> () -> ()  <- () -> () -> None
        #                 mid
        #                  |
        #                  V
        #                 None
        #
        # 
        #                  s        f
        #      () -> () -> ()  <-  () -> None
        #           mid1  mid2
        #                  |
        #                  V
        #                 None

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

        # Iterate reversal until we reach end of right half
        # tc: O(n/2) ~ O(n) 
        while curr:

            # Grab next node before severing connection
            nextNode = curr.next

            # Flip connection, reversing node
            curr.next = prev

            # Advance to flip next node
            prev = curr
            curr = nextNode

        # Curr is at None
        # Prev is at the original tail which is now the new head
        newRightHead = prev


        # -----------------------------------------
        # 3. Merge Left and Reversed Right List Alternating
        # - left = start of left half
        # - right = start of reversed right half
        left = head
        right = newRightHead

        # Right Half Equal Or Shorter:
        #   - left half is equal or has 1 extra node (the mid element) 
        #   - but left and right half always share slow
        #   - once right reaches slow, we've reached the shared portion of the list
        #   - the shared portion acts as a prepared tail and tells us when right terminates

        # Prepared Tail (Shared Mid):

        # Odd lists:
        #   - slow ends on mid for odd lists

        #    - - - - L - - -     - - R - - 
        #                  s             f
        #   (1) -> (2) -> (3) -> (4) -> (5)       (1) -> (2) -> (3) -> None       (1) -> (5) -> (2) -> (4) -> (3) -> None
        #                 mid                ==>     (5) -> (4) -> (3) -> None      ==> 
        #                                                           ^
        #                                                        right reaches shared slow,
        #                                                        notice how "(3) -> None" is already prepared
        
        # Even lists:
        #   - slow mid2 for even lists
        #
        #    - - L - -     - - R - -                           
        #                  s      f          
        #   (1) -> (2) -> (3) -> (4)               (1) -> (2) -> (3) -> None       (1) -> (4) -> (2) -> (3) -> None
        #           mid1  mid2                ==>      (4) -> (3) -> None            ==> 
        #                                                      ^
        #                                                    right reaches shared slow,
        #                                                    notice how "(4) -> (3) -> None" is already prepared

        # tc: O(n/2) ~ O(n) 
        while right != slow:

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

            # Merge lists alternating
            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 
  
        # When right == slow, its a valid node so we can set its .next to None
        # but this is redundant since we already pointed slow to None during the reversal phase,
        # so right.next.next = None is actually doing None.next = None,
        # which is why we get the error: 'NoneType' object has no attribute 'next'

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

Sol: Odd-Even Grouping:
1. if head is null:
    a. return head
2. odd = head
3. even = head.next
4. evenHead = even
5. while even and even.next:
    a. odd.next = even.next
    b. odd = odd.next
    c. even.next = odd.next
    d. even = even.next
6. odd.next = evenHead
7. return head

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

        # Odd-Even Grouping:
        #   - All odd-indexed nodes are relinked together, followed by all even-indexed nodes
        #   - Relative order within each group is preserved
        #   - Achieved in a single pass by weaving two interleaved pointers forward

        # Grouping Phase (1-indexed):

        # Input:    1 -> 2 -> 3 -> 4 -> 5 -> null
        #           odd  even

        # Step 1:   1 -> 3    2 -> 4 -> 5 -> null
        #                odd       even

        # Step 2:   1 -> 3 -> 5 -> null   2 -> 4 -> null
        #                     odd              even

        # Final:    1 -> 3 -> 5 -> 2 -> 4 -> null

        # Idea:
        #   - Use two pointers, odd and even, starting at nodes 1 and 2
        #   - Weave odd forward through odd-indexed nodes, even forward through even-indexed nodes
        #   - Save the head of the even list before it's disconnected from the odd list
        #   - Once even runs out, attach the saved even list to the end of the odd list

        # 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

        # base case:
        # empty list is already "grouped"
        if not head:
            return head

        evenDummyHead = even
        evenCurr = head.next

        oddCurr = head


        # weave odd/even pointers forward, relinking each to skip the other group
        # tc: O(n)
        while even and even.next:

            # Index 1, 3, 5 -> odd indexed
            odd.next = even.next
            odd = odd.next

            # Index 2, 4, 6 -> even indexed
            even.next = odd.next
            even = even.next

        # Odd list becomes left hand side new list
        # Even list becomes right hand side of new list 
        # Attach the tail of the odd list to head of even list
        odd.next = evenHead

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

Sol 1: Two Dummy Head Bucket Split:
1. lessDummyHead = ListNode(-1)
2. lessTail = lessDummyHead
3. greaterDummyHead = ListNode(-1)
4. greaterTail = greaterDummyHead
5. curr = head
6. while curr:
    a. if curr.val < x:
        lessTail.next = curr
        lessTail = lessTail.next
    b. else:
        greaterTail.next = curr
        greaterTail = greaterTail.next
    c. curr = curr.next
7. greaterTail.next = None
8. lessTail.next = greaterDummyHead.next
9. return lessDummyHead.next

    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:

        # Dual Dummy-Head Split:
        #   - Every node is routed into one of two chains: less-than-x, or greater-or-equal-to-x
        #   - Both chains are built in relative original order
        #   - Join the left and right list at the end

        # Partition Phase:

        # Input:    1 -> 4 -> 3 -> 2 -> 5 -> 2 -> None,  x = 3

        # Route:    less:    1 -> 2 -> 2 -> None
        #           greater: 4 -> 3 -> 5 -> None

        # Splice:   1 -> 2 -> 2 -> 4 -> 3 -> 5 -> None

        # Idea:
        #   - Walk the original list once, routing each node to the less or greater chain
        #   - Use 2 dummyHeads to have access to both partition lists
        #   - After the pass, turn the right side greater chain into a tail,
        #     grab the head of the left less list, and connect the left to right list

        # Original list iterator
        curr = head

        # List1 iterator
        lessDummyHead = ListNode(-1)
        lessCurr = lessDummyHead

        # List 2 iterator
        greaterDummyHead = ListNode(-1)
        greaterCurr = greaterDummyHead

        # Iterate over original linked list, and partition into less or greater than
        # tc: O(n)
        while curr:

            # Send anything less than the value to the less list
            if curr.val < x:
                lessCurr.next = curr
                lessCurr = lessCurr.next

            # Everything else to the greater list
            else:
                greaterCurr.next = curr
                greaterCurr = greaterCurr.next

            # Check next node in original list
            curr = curr.next

        # List 2 will become the right hand side of the list, and holds the tail of the new list
        greaterCurr.next = None

        # List 1 will become the left hand side of the list, and holds the head of the new list 
        # and will connect the left and right half of the list
        lessCurr.next = greaterDummyHead.next

        # Grab new head of list
        newHead = lessDummyHead.next

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

Sol 1: In Place Insertion Sort With Optimal Avoiding DummyHead Restart:
1. dummyHead = ListNode(0)
2. curr = head
3. prev = dummyHead
4. while curr:
    a. nextUnsorted = curr.next
    b. if prev.val >= curr.val:
        prev = dummyHead
    c. while prev.next and prev.next.val < curr.val:
        prev = prev.next
    d. curr.next = prev.next
    e. prev.next = curr
    f. curr = nextUnsorted
5. return dummyHead.next

    def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        
        # In Place Insertion Sort:
        #   - A sorted portion is grown one node at a time, starting empty
        #   - Each node from the unsorted input is inserted into its correct position
        #   - A dummy head lets the sorted portion start from nothing without special-casing

        # Sorting Phase:

        # Input:    4 -> 2 -> 1 -> 3 -> None

        # Step 1:   sorted: 4 -> None                  (sorted list was empty, insert 4, )

        # Step 2:   sorted: 2 -> 4 -> None              (compare 4 and 2, swap)

        # Step 3:   sorted: 1 -> 2 -> 4 -> None          (compare 4 and 1, swap, compare 2 and 1, swap)

        # Step 4:   sorted: 1 -> 2 -> 3 -> 4 -> None      (compare 4 and 3, swap, compare 2 and 3, stay in place)

        # Idea:
        #   - curr walks the original unsorted list, one node at a time
        #   - For each curr, walk swap from left to right starting at dummyHead to find where it belongs
        #   - Splice curr in between prev and prev.next
        #   - Save curr.next before overwriting it, or the rest of the unsorted list is lost

        # 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

        # Each new node walks sorted partial list from dummyHead to right
        # tc: O(n^2)
        while curr != None:

            # Grab next node before overwriting curr.next
            nextUnsorted = curr.next

            # Insertion Sort Quick Start Optimization:
            # avoid restarting completely at dummyHead,
            # if new element should go in front of the element we just inserted
            if curr.val <= prev.val:
                prev = dummyHead

            # Walk curr to correct point in sorted partial list:
            #   - end of sorted list (prev.next != None)
            #   - found correct spot for curr (prev <= curr <= prev.next)
            while prev.next != None and prev.next.val < curr.val:
                prev = prev.next

            # Place curr at correct spot in sorted partial list 
            curr.next = prev.next
            prev.next = curr

            # Advance iterator to next unsorted node
            curr = nextUnsorted

        # Grab head of new sorted list
        newHead = dummyHead.next

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

Sol 1: Top-Down Recursive Merge Sort:
1. if head is null or head.next is null:
    a. return head
2. slow = head, fast = head.next
3. while fast and fast.next:
    a. slow = slow.next
    b. fast = fast.next.next
4. mid = slow.next
5. slow.next = null
6. left = sortList(head)
7. right = sortList(mid)
8. dummyHead = ListNode(0)
9. curr = dummyHead
10. while left and right:
    a. if left.val <= right.val:
        - curr.next = left
        - left = left.next
    b. else:
        - curr.next = right
        - right = right.next
    c. curr = curr.next
11. curr.next = left or right
12. return dummyHead.next

Sol 2: Bottom-Up Iterative Merge Sort:
1. if head is null or head.next is null:
    a. return head
2. n = 0, node = head
3. while node:
    a. n = n + 1
    b. node = node.next
4. dummyHead = ListNode(0, head)
5. size = 1
6. while size < n:
    a. curr = dummyHead.next
    b. tail = dummyHead
    c. while curr:
        - left = curr
        - right = split(left, size)
        - curr = split(right, size)
        - merged, mergedTail = merge(left, right)
        - tail.next = merged
        - mergedTail.next = curr
        - tail = mergedTail
    d. size = size * 2
7. return dummyHead.next

Helper split(head, size):
1. for i in range(size - 1):
    a. if not head: return null
    b. head = head.next
2. if not head: return null
3. rest = head.next
4. head.next = null
5. return rest

Helper merge(l1, l2):
1. dummyHead = ListNode(0)
2. curr = dummyHead
3. while l1 and l2:
    a. if l1.val <= l2.val:
        - curr.next = l1
        - l1 = l1.next
    b. else:
        - curr.next = l2
        - l2 = l2.next
    c. curr = curr.next
4. curr.next = l1 or l2
5. while curr.next:
    a. curr = curr.next
6. return dummyHead.next, curr

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

        # Merge Sort:
        #   - List is recursively split in half until sublists of size 0 or 1 remain
        #   - Sorted sublists are merged back together on the way up the recursion
        #   - Each level of recursion doubles the size of the merged result

        # Splitting Phase (Top-Down):

        # Level 0:       [8, 4, 7, 3, 2, 6, 5, 1]        2^0 = 1 subarrays  (n elements, O(n))
        #                    /              \
        # Level 1:    [8, 4, 7, 3]      [2, 6, 5, 1]     2^1 = 2 subarrays  (n/2 elements, O(n/2))
        #                /     \          /     \
        # Level 2:    [8, 4] [7, 3]     [2, 6] [5, 1]    2^2 = 4 subarrays  (n/4 elements, O(n/4))
        #              /  \    /   \     /   \   /  \
        # Level 3:    [8] [4] [7] [3]   [2] [6] [5] [1]  2^3 = 8 subarrays  (n/8 element, O(1))

        # Idea:
        #   - Use slow/fast pointers to find the midpoint of the list
        #   - Split the list into two halves at the midpoint
        #   - Recurse on each half until reaching base case (0 or 1 nodes)
        #   - Merge the two sorted halves as recursion unwinds

        # Note:
        # 1. Find midpoint with slow/fast pointers, split list in two
        # 2. Recurse on each half
        # 3. Merge the two sorted halves
        # 4. Base case: 0 or 1 nodes, already sorted

        # base case:
        # list is already sorted
        if not head or not head.next:
            return head

        # find midpoint using slow/fast pointers
        # tc: O(n)
        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 is start of right half
        mid = slow.next
        slow.next = None

        # recurse on each half
        # tc: O(log n) levels of recursion
        left = self.sortList(head)
        right = self.sortList(mid)

        # merge sorted halves
        dummyHead = ListNode(0)
        curr = dummyHead

        # tc: O(n) total work across this level
        while left and right:

            # grab smaller value between the two and iterate that list
            if left.val <= right.val:
                curr.next = left
                left = left.next
            else:
                curr.next = right
                right = right.next

            curr = curr.next

        # one list is empty,
        # connect remaining portion of non-empty list
        curr.next = left or right

        # overall: tc O(n log n) — log n levels of recursion, O(n) merge work per level
        # overall: sc O(log n) — recursion stack depth
        return dummyHead.next

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

        # Merge Sort:
        #   - List is divided into sublists of length size
        #   - Adjacent sublist pairs are merged into sorted groups of length (size * 2)
        #   - size doubles each round until it covers the whole list

        # Merging Phase (Bottom-Up):

        # Round 0:    [8] [4] [7] [3] [2] [6] [5] [1]    size = 1   (8 subarrays, O(1) each)
        #               \ /     \ /     \ /     \ /
        # Round 1:     [4, 8] [3, 7]   [2, 6] [1, 5]     size = 2   (4 subarrays, O(2) each)
        #                 \      /         \      /
        # Round 2:      [3, 4, 7, 8]     [1, 2, 5, 6]    size = 4   (2 subarrays, O(4) each)
        #                      \                /
        # Round 3:         [1, 2, 3, 4, 5, 6, 7, 8]      size = 8   (1 subarray, O(8))

        # Idea:
        #   - Start with sublists of size 1 (each already "sorted")
        #   - Walk the list splitting off and merging pairs of sublists,
        #     reattaching each merged group to the end of the result so far
        #   - Double `size` and repeat until size >= length, at which point
        #     the entire list has been merged into one sorted list

        # Note:
        # 1. Count list length
        # 2. Instead of recursing top-down, merge bottom-up
        # 3. Start with sublist size=1, merge sorted pairs of that size,
        #    doubling size each round until size >= length
        # 4. Splitting and merging only rewires existing nodes,
        #    no new nodes or recursion needed

        # Helper: 
        # split off a sublist of length size starting at head,
        # sever the link, and return the head of the remainder
        def split(head, size):

            # tc: O(size)
            for _ in range(size - 1):
                if not head:
                    return None
                head = head.next

            if not head:
                return None

            # sever link between left sublist and remainder
            rest = head.next
            head.next = None

            # overall: tc O(size)
            # overall: sc O(1)
            return rest

        # Helper: merge two sorted sublists, return (mergedHead, mergedTail)
        def merge(l1, l2):

            dummyHead = ListNode(0)
            curr = dummyHead

            # tc: O(n), n = combined length of l1 and l2
            while l1 and l2:

                # grab smaller value between the two and iterate that list
                if l1.val <= l2.val:
                    curr.next = l1
                    l1 = l1.next
                else:
                    curr.next = l2
                    l2 = l2.next

                curr = curr.next

            # one list is empty,
            # connect remaining portion of non-empty list
            curr.next = l1 or l2

            # advance curr to the tail of the merged list
            while curr.next:
                curr = curr.next

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

        # 0 or 1 node:
        # list is already sorted
        if not head or not head.next:
            return head

        # 1. Count list length
        n = 0
        node = head
        while node:
            n += 1
            node = node.next

        # dummyHead:
        # allows uniform access to the front of the list across rounds
        dummyHead = ListNode(0, head)

        # Size:
        # Length of sublists to merge this round (start with length 1, then 2, 4, 8, etc...)
        # tc: O(log n) rounds total, size doubles each round
        size = 1
        while size < n:

            # Track head of curr sublist we are merging
            curr = dummyHead.next

            # tail tracks the end of the last merged group,
            # so we can attach the next merged group after it
            tail = dummyHead

            # merge consecutive pairs of sublists of length 'size'
            # tc: O(n) total work across this round
            while curr:

                # split off left sublist of size `size`
                left = curr
                right = split(left, size)

                # split off right sublist of size `size`,
                # curr becomes the start of the remainder
                curr = split(right, size)

                # merge left and right sublists
                merged, mergedTail = merge(left, right)

                # connect previous tail to this round's merged group
                tail.next = merged

                # connect this merged group's tail to the remainder
                mergedTail.next = curr

                # advance tail for the next merged group
                tail = mergedTail

            # Double size for next round
            size *= 2

        # overall: tc O(n log n) — log n rounds, O(n) work per round
        # overall: sc O(1) — only reuses existing nodes, no recursion
        return dummyHead.next

Sol 1: Circular Shift:
1. if not head or not head.next:
    a. return head
2. n = 1, tail = head
3. while tail.next:
    a. tail = tail.next
    b. n = n + 1
4. k = k % n
5. if k == 0:
    a. return head
6. tail.next = head
7. newTail = head
8. for i in range(n - k - 1):
    a. newTail = newTail.next
9. newHead = newTail.next
10. newTail.next = null
11. return newHead

    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:

        # Circular Shift:
        #   - List is temporarily joined into a circle: tail -> head
        #   - New tail is found at position (n - k % n - 1) from the old head
        #   - Breaking the circle after the new tail yields the rotated list

        # Rotation Phase:

        # Input:    0 -> 1 -> 2 -> 3 -> 4 -> null,  k = 2, n = 5
        #           effective shift = k % n = 2

        # Step 1:   0 -> 1 -> 2 -> 3 -> 4 -
        #           ^                     |
        #           | - - - - - - - - - - -   (circular)

        # Step 2:   tail: (n - k - 1) = 2
        #           head  (n - k)     = 3

        # Step 3:   0 -> 1 -> 2 -> null      3 -> 4 -> 0 -> 1 -> 2 -> null

        # Idea:
        #   - Find the length of the list and its tail
        #   - Connect tail to head, forming a circular list
        #   - Walk (n - k % n - 1) steps from head to find the new tail
        #   - Break the circle by setting newTail.next = None

        # Note:
        # 1. k can be larger than list length, so use k % n to get effective shift
        # 2. If k % n == 0, no rotation needed, return head unchanged
        # 3. Joining into a circle avoids a second pass to relink the ends

        # Empty List Or Single Node:
        # Already rotated
        if not head or not head.next:
            return head

        # Length of list to calculate new tail index
        # tc: O(n)
        n = 1
        curr = head
        while curr.next != None:
            curr = curr.next
            n += 1

        tail = curr

        # Early No Rotation:
        # shift ends up back at start, no rotation needed
        k %= n
        if k == 0:
            return head

        # List into circle:
        # connect tail to head
        tail.next = head

        # Walk to 1 before the new head,
        # giving us the new tail
        # tc: O(n)
        newTail = head
        for _ in range(n - k - 1):
            newTail = newTail.next

        # Grab the new head
        newHead = newTail.next

        # Circle into list:
        # sever connection from new tail to new head
        newTail.next = None

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

Sol 2: Fixed Gap Two Pointers:
1. dummyHead = ListNode(-1, head)
2. slow = fast = dummyHead
3. i = 0
4. while i != k + 1:
    a. i = i + 1
    b. fast = fast.next
5. while fast:
    a. fast = fast.next
    b. slow = slow.next
6. slow.next = slow.next.next
7. return dummyHead.next

    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        
        # Two-Pass Length Offset:
        #   - Total list length is computed on a first pass
        #   - The node just before the target is located at index (length - n) from a dummy head
        #   - Skipping that node's next pointer removes the target in a single splice

        # Removal Phase:

        # Input:    1 -> 2 -> 3 -> 4 -> 5 -> null,  n = 2,  listLen = 5
        #           removeDist = listLen - n = 3

        # Pass 1:   dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null   (walk full list, count length)

        # Pass 2:   dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
        #                              curr (walked 3 steps from dummy)

        # Splice:   dummy -> 1 -> 2 -> 3 -> 5 -> null        (curr.next skipped, node 4 removed)

        # Idea:
        #   - Traverse the list once to calculate total length
        #   - Use a dummy node to handle edge cases (like removing head)
        #   - Traverse again from dummy, stopping at the node just before the removal index
        #   - Point prior.next = prior.next.next, disconnecting the removal node

        # 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

        # 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
        dummyHead = ListNode(-1, head)
        curr = dummyHead

        # Second Pass: walk to node just before the target node
        # tc: O(n)
        removeDist = listLen - n
        i = 0
        while i != removeDist:
            i += 1
            curr = curr.next

        # arrived at (n-1)th node from target: skip the target node
        curr.next = curr.next.next

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

    def removeNthFromEnd(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:

        # Fixed-Gap Two Pointers:
        #   - fast is sent ahead by (k + 1) steps, opening a gap of k nodes between slow and fast
        #   - Both pointers then advance together, so the gap stays fixed
        #   - When fast runs off the end, slow lands just before the target node

        # Removal Phase:

        # Input:    1 -> 2 -> 3 -> 4 -> 5 -> null,  k = 2
        #     dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
        #     slow

        # Step 1:   fast advances (k + 1) = 3 steps from dummy
        #     dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
        #     slow                   fast

        # Step 2:   advance slow and fast together until fast hits null
        #     dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
        #                        slow             fast (now null)

        # Splice:   dummy -> 1 -> 2 -> 3 -> 5 -> null   (slow.next skipped, node 4 removed)

        # Idea:
        #   - Send fast ahead by (k + 1) steps from a dummy head, opening a gap of k nodes
        #   - Advance slow and fast together, preserving that gap, until fast falls off the list
        #   - slow now sits just before the node k from the end; skip it to remove

        # Note:
        # 1. Use two pointers spaced k apart (fast and slow)
        # 2. Move both pointers together until fast hits the 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
        dummyHead = ListNode(-1, head)
        slow = fast = dummyHead

        # send fast ahead by (k + 1) steps to open a gap of k nodes
        # tc: O(k)
        i = 0
        while i != k + 1:
            i += 1
            fast = fast.next

        # advance both pointers together, preserving the gap, until fast falls off the list
        # tc: O(n)
        while fast:
            fast = fast.next
            slow = slow.next

        # slow is pointing to the node just before the target: skip it
        slow.next = slow.next.next

        newHead = dummyHead.next

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

Sol 3: Modified Floyd Cycle:
1. slow = nums[0]
2. fast = nums[0]
3. while true:
    a. slow = nums[slow]
    b. fast = nums[nums[fast]]
    c. if slow == fast: break
4. slow = nums[0]
5. while true:
    a. if slow == fast: break
    b. slow = nums[slow]
    c. fast = nums[fast]
6. 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