Linked List Patterns

# TEMPLATE 1: Dummy node + prev/curr (insert, delete, partition, merge)
def template_dummy(head):
    dummy = ListNode(0, head)   # Sentinel before head -- never moves
    prev = dummy                 # Tracks the node before curr
    curr = head                  # The node being inspected
    while curr:
        # ... decide whether to keep, modify, or delete curr ...
        # To DELETE curr:  prev.next = curr.next; curr = curr.next
        # To KEEP curr:    prev = curr; curr = curr.next
        pass
    return dummy.next            # Always correct -- even if original head was removed

# TEMPLATE 2: Fast/slow pointers (cycle detection, find middle, Nth from end)
def template_fast_slow(head):
    slow = fast = head
    while fast and fast.next:    # Stop when fast falls off the end
        slow = slow.next         # 1 step
        fast = fast.next.next    # 2 steps
        # if slow == fast: cycle detected
    # When loop exits: slow is at the middle (second middle for even length)
    return slow

# TEMPLATE 3: Reverse in place (full or sublist reversal)
def template_reverse(head):
    prev, curr = None, head
    while curr:
        nxt = curr.next          # 1. Save -- never lose the rest of the list
        curr.next = prev         # 2. Flip the pointer backwards
        prev = curr              # 3. Advance prev forward
        curr = nxt               # 4. Advance curr forward
    return prev                  # prev is the new head

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def has_cycle(head):
    """Detect cycle in linked list using Floyd's tortoise and hare."""
    # Both pointers start at the head of the list
    slow = fast = head
    
    while fast and fast.next:
        slow = slow.next          # Tortoise moves 1 step
        fast = fast.next.next     # Hare moves 2 steps
        if slow == fast:
            return True           # They met -- cycle confirmed
    
    # Fast pointer reached the end, so no cycle exists
    return False

def find_middle(head):
    """Find middle node (second middle if even length).
    
    Example: 1 -> 2 -> 3 -> 4 -> 5  returns node 3
             1 -> 2 -> 3 -> 4       returns node 3 (second middle)
    """
    slow = fast = head
    
    while fast and fast.next:
        slow = slow.next          # 1 step
        fast = fast.next.next     # 2 steps
    
    # When fast reaches the end, slow is at the middle
    return slow

def reverse_list(head):
    """Reverse entire linked list in-place.
    
    Walkthrough with 1 -> 2 -> 3:
      Step 1: prev=None, curr=1  =>  1.next = None,  prev=1, curr=2
      Step 2: prev=1,    curr=2  =>  2.next = 1,     prev=2, curr=3
      Step 3: prev=2,    curr=3  =>  3.next = 2,     prev=3, curr=None
    Result: 3 -> 2 -> 1
    """
    prev = None
    current = head
    
    while current:
        next_node = current.next   # Save the next node before we break the link
        current.next = prev        # Reverse the pointer: point backwards
        prev = current             # Advance prev to current node
        current = next_node        # Move forward in the original list
    
    return prev  # prev is now the new head

def reverse_between(head, left, right):
    """Reverse nodes from position left to right (1-indexed).
    
    Example: 1 -> 2 -> 3 -> 4 -> 5, left=2, right=4
    Result:  1 -> 4 -> 3 -> 2 -> 5
    
    The trick: repeatedly take the node after current and insert it
    right after prev, effectively building the reversed segment.
    """
    dummy = ListNode(0, head)
    prev = dummy
    
    # Step 1: Navigate prev to the node just before position 'left'
    for _ in range(left - 1):
        prev = prev.next
    
    # Step 2: Reverse the sublist from left to right
    current = prev.next
    for _ in range(right - left):
        next_node = current.next        # Node to be moved to the front
        current.next = next_node.next   # Detach next_node from its position
        next_node.next = prev.next      # Insert next_node right after prev
        prev.next = next_node           # Update prev's next to next_node
    
    return dummy.next

def merge_two_lists(l1, l2):
    """Merge two sorted linked lists into one sorted list.
    
    Example: l1 = 1 -> 3 -> 5,  l2 = 2 -> 4 -> 6
    Result:  1 -> 2 -> 3 -> 4 -> 5 -> 6
    """
    dummy = ListNode(0)       # Dummy head avoids edge cases for the first node
    current = dummy
    
    while l1 and l2:
        if l1.val <= l2.val:  # Pick the smaller value to maintain sorted order
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next
    
    # Attach whichever list still has remaining nodes
    current.next = l1 or l2
    return dummy.next

def remove_nth_from_end(head, n):
    """Remove the nth node from the end of the list.
    
    Example: 1 -> 2 -> 3 -> 4 -> 5, n=2
    Gap setup: fast is 3 nodes ahead of slow (n+1 = 3)
    When fast = None, slow points to node 3 => remove node 4
    Result:  1 -> 2 -> 3 -> 5
    """
    dummy = ListNode(0, head)
    slow = fast = dummy
    
    # Create a gap of n+1 between fast and slow
    for _ in range(n + 1):
        fast = fast.next
    
    # Advance both pointers until fast reaches the end
    while fast:
        slow = slow.next
        fast = fast.next
    
    # slow.next is the node to remove -- skip over it
    slow.next = slow.next.next
    return dummy.next