Linked List

# Iterative solution
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
    prev = None
    while head:
        head.next, prev, head = prev, head, head.next
    return prev

# Recursive solution
def reverseListRecursive(self, head: ListNode) -> ListNode:
    # Base case: empty list or list with only one node
    if not head or not head.next:
        return head

    # Recursively reverse the rest of the list after head
    new_head = self.reverseListRecursive(head.next)

    # The node after head now points back to head
    head.next.next = head

    # Head becomes the new tail, so it points to None
    head.next = None

    # Return the new head of the reversed list
    return new_head

def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
    # Iterative solution using the two-pointer technique
    # Dummy node to handle edge cases
    dummy = ListNode(0)
    dummy.next = head

    # Two pointers: fast and slow
    fast = dummy
    slow = dummy

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

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

    # Remove the nth node from the end
    slow.next = slow.next.next

    return dummy.next

# Recursive solution
def removeNthFromEndRecursive(self, head: ListNode, n: int) -> ListNode:
    # We'll use a helper function that returns the position from the end
    def remove_helper(node, n):
        # Base case: we've reached the end of the list
        if not node:
            return 0

        # Recursively process the rest of the list
        position = remove_helper(node.next, n) + 1

        # If this is the (n+1)th node from the end, remove the nth node
        if position == n + 1:
            node.next = node.next.next

        return position

    # Create a dummy node to handle edge cases
    dummy = ListNode(0)
    dummy.next = head

    # Start the recursive process
    remove_helper(dummy, n)

    return dummy.next

def middleNode(self, head: ListNode) -> ListNode:
    # Iterative solution using fast and slow pointers
    # Initialize slow and fast pointers
    slow = head
    fast = head

    # Move slow one step and fast two steps at a time
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    # When fast reaches the end, slow is at the middle
    return slow

# Recursive solution using a two-pass approach
def middleNodeRecursive(self, head: ListNode) -> ListNode:
    # First pass: count the number of nodes
    def count_nodes(node):
        if not node:
            return 0
        return 1 + count_nodes(node.next)

    # Second pass: find the middle node
    def find_middle(node, current, target):
        if current == target:
            return node
        return find_middle(node.next, current + 1, target)

    # Count the nodes and calculate the middle position
    length = count_nodes(head)
    middle_pos = length // 2  # Integer division gives the second middle for even lengths

    # Find the middle node
    return find_middle(head, 0, middle_pos)

def deleteNode(self, node):
    # Since we don't have access to the previous node,
    # we can't delete the node directly.
    # Instead, we'll copy the next node's value to
    # the current node and delete the next node

    # Copy the next node's value
    node.val = node.next.val

    # Delete the next node
    del_node = node.next
    node.next = node.next.next
    del del_node

def addTwoNumbers(self, l1, l2):
    dummy = curr = ListNode(0)
    carry = 0
    while l1 or l2 or carry:
        carry, val = divmod(
            (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry, 10)
        curr.next = ListNode(val)
        curr = curr.next
        if l1: l1 = l1.next
        if l2: l2 = l2.next
    return dummy.next

# Recursive solution
def addTwoNumbersRecursive(self, l1: ListNode, l2: ListNode, carry=0) -> ListNode:
    # Base case: if both lists are empty and no carry
    if not l1 and not l2 and not carry:
        return None

    # Get values (or 0 if the list has ended)
    x = l1.val if l1 else 0
    y = l2.val if l2 else 0

    # Calculate sum and new carry
    total = x + y + carry
    carry = total // 10
    digit = total % 10

    # Create a new node with the digit value
    result = ListNode(digit)

    # Recursively process the next digits
    result.next = self.addTwoNumbersRecursive(
        l1.next if l1 else None,
        l2.next if l2 else None,
        carry
    )

    return result

def reverse(self, curr):
    prev = None
    while curr:
        curr.next, prev, curr = prev, curr, curr.next
    return prev

def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
    return self.reverse(self.addTwoNumbersI(self.reverse(l1), self.reverse(l2)))

# there are stored left to right...
# can reduce to Add Two Numbers I, by reversing both.
# and then reverse the answer

def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
    # Iterative solution using dummy node pattern
    # Create a dummy node
    dummy = ListNode(0)
    current = dummy

    # Compare nodes from both lists and link the smaller one
    while l1 and l2:
        if l1.val <= l2.val:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next

    # Link the remaining nodes (if any)
    current.next = l1 if l1 else l2

    # Return the merged list (excluding the dummy node)
    return dummy.next

# Recursive solution
def mergeTwoListsRecursive(self, l1: ListNode, l2: ListNode) -> ListNode:
    # Base cases
    if not l1:
        return l2
    if not l2:
        return l1

    # Recursive case: determine which node should come first
    if l1.val <= l2.val:
        # l1 comes first, so l1.next should be merged with l2
        l1.next = self.mergeTwoListsRecursive(l1.next, l2)
        return l1
    else:
        # l2 comes first, so l2.next should be merged with l1
        l2.next = self.mergeTwoListsRecursive(l1, l2.next)
        return l2

# Approach 1: Sequential Merging
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
    if not lists:
        return None

    result = lists[0]
    # Sequentially merge each list with the result
    for i in range(1, len(lists)):
        result = self.mergeTwoLists(result, lists[i])

    return result
# Time: O(N*k), Space: O(1)

# Approach 2: Divide and Conquer (More Efficient)
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
    if not lists:
        return None

    # Merge lists using divide and conquer
    def merge(lists, start, end):
        if start == end:
            return lists[start]
        if start > end:
            return None

        mid = start + (end - start) // 2
        left = merge(lists, start, mid)
        right = merge(lists, mid + 1, end)
        return mergeTwoLists(left, right)

    return merge(lists, 0, len(lists) - 1)
# Time: O(N*log(k)), Space: O(log(k))

# Approach 3: Using a Priority Queue (Heap)
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
    pq = [(node.val, i, node) for i, node in enumerate(lists) if node]
    heapify(pq)
    dummy = ListNode(-1)
    curr = dummy

    while pq:
        _, i, top_node = heappop(pq)

        curr.next = top_node
        curr = top_node

        if top_node.next:
            heappush(pq, (top_node.next.val, i, top_node.next))

    return dummy.next
# Time: O(N*log(k)), Space: O(k)

def rotateRight(self, head: ListNode, k: int) -> ListNode:
    # Edge cases
    if not head or not head.next or k == 0:
        return head

    # Step 1: Find the length of the list and the tail node
    current = head
    length = 1
    while current.next:
        current = current.next
        length += 1

    # The last node (tail) is now in current
    tail = current

    # Step 2: Calculate the effective rotation
    # If k = length, we end up with the original list
    k = k % length
    if k == 0:
        return head

    # Step 3: Form a cycle by connecting tail to head
    tail.next = head

    # Step 4: Find the new tail position
    # We need to go to the (length - k)th node
    current = head
    for _ in range(length - k - 1):
        current = current.next

    # Step 5: Break the cycle at the right position
    new_head = current.next
    current.next = None

    return new_head

def partition(self, head: ListNode, x: int) -> ListNode:
    # Create dummy heads for two separate lists
    smaller_dummy = ListNode(0)
    greater_dummy = ListNode(0)

    # Pointers to track the current end of each list
    smaller = smaller_dummy
    greater = greater_dummy

    # Traverse the original list
    current = head
    while current:
        if current.val < x:
            # Add to smaller list
            smaller.next = current
            smaller = smaller.next
        else:
            # Add to greater/equal list
            greater.next = current
            greater = greater.next

        # Move to next node
        current = current.next

    # Connect the two lists
    greater.next = None  # Important: prevent cycles!
    smaller.next = greater_dummy.next

    return smaller_dummy.next

def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
    dummy = ListNode(-1, head)  # NEED THE DUMMY!!! WHAT IF WE REVERSE THE ENTIRE LIST!!!

    prev, curr = dummy, head
    for _ in range(left - 1):
        curr, prev = curr.next, curr

    prev_node_before_reverse = prev  # 1
    first_node_reversed = curr  # 2

    for _ in range(right - left + 1):
        curr.next, curr, prev = prev, curr.next, curr

    first_node_after_reverse = curr  # 5
    last_node_reversed = prev  # 4

    prev_node_before_reverse.next = last_node_reversed
    first_node_reversed.next = first_node_after_reverse

    return dummy.next

"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""

# KEY IDEA: use map between nodes in the original list and nodes in the
# copied list for fast O(1) setting of random ptrs
# O(n) time, O(n) space

# step 1. copy the new linked list with only values and next ptrs
# step 2. fill in the random pointers for the new linked list

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head: return head
        old_to_new_map = {}
        og_head = head
        prev_new_node = None
        curr_old_node = head

        while curr_old_node:
            new_node = Node(curr_old_node.val)
            if prev_new_node:
                prev_new_node.next = new_node
            prev_new_node = new_node
            old_to_new_map[curr_old_node] = new_node
            curr_old_node = curr_old_node.next

        # fill in random nodes now
        curr_old_node = og_head
        while curr_old_node:
            if curr_old_node.random:
                old_to_new_map[curr_old_node].random = old_to_new_map[curr_old_node.random]
            curr_old_node = curr_old_node.next

        return old_to_new_map[og_head]