Singly Linked List

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

class SinglyLinkedList:
    def __init__(self):
        self.head = None
        self.size = 0
    
    def __str__(self):
        curr = self.head
        nodes = []
        while curr:
            nodes.append(str(curr.val))
            curr = curr.next
        return ' -> '.join(nodes)

def insert_at_beginning(self, val: int) -> None:
    """
    Time Complexity: O(1)
    """
    new_node = ListNode(val)
    new_node.next = self.head
    self.head = new_node
    self.size += 1

def insert_at_end(self, val: int) -> None:
    """
    Time Complexity: O(n)
    """
    new_node = ListNode(val)
    if not self.head:
        self.head = new_node
        self.size += 1
        return
    
    curr = self.head
    while curr.next:
        curr = curr.next
    curr.next = new_node
    self.size += 1

def insert_at_position(self, val: int, position: int) -> None:
    """
    Time Complexity: O(n)
    """
    if position < 0 or position > self.size:
        raise ValueError("Invalid position")
        
    if position == 0:
        self.insert_at_beginning(val)
        return
    
    new_node = ListNode(val)
    curr = self.head
    for _ in range(position - 1):
        curr = curr.next
    
    new_node.next = curr.next
    curr.next = new_node
    self.size += 1

def insert_sorted(self, val: int) -> None:
    """
    Insert in sorted order
    Time Complexity: O(n)
    """
    new_node = ListNode(val)
    
    if not self.head or self.head.val >= val:
        new_node.next = self.head
        self.head = new_node
        self.size += 1
        return
    
    curr = self.head
    while curr.next and curr.next.val < val:
        curr = curr.next
    
    new_node.next = curr.next
    curr.next = new_node
    self.size += 1

def delete_at_beginning(self) -> None:
    """
    Time Complexity: O(1)
    """
    if not self.head:
        raise ValueError("List is empty")
    
    self.head = self.head.next
    self.size -= 1

def delete_at_end(self) -> None:
    """
    Time Complexity: O(n)
    """
    if not self.head:
        raise ValueError("List is empty")
    
    if not self.head.next:
        self.head = None
        self.size -= 1
        return
    
    curr = self.head
    while curr.next.next:
        curr = curr.next
    curr.next = None
    self.size -= 1

def delete_at_position(self, position: int) -> None:
    """
    Time Complexity: O(n)
    """
    if not self.head or position < 0 or position >= self.size:
        raise ValueError("Invalid position")
    
    if position == 0:
        self.delete_at_beginning()
        return
    
    curr = self.head
    for _ in range(position - 1):
        curr = curr.next
    
    curr.next = curr.next.next
    self.size -= 1

def delete_value(self, val: int) -> None:
    """
    Delete first occurrence of value
    Time Complexity: O(n)
    """
    if not self.head:
        raise ValueError("List is empty")
    
    if self.head.val == val:
        self.head = self.head.next
        self.size -= 1
        return
    
    curr = self.head
    while curr.next and curr.next.val != val:
        curr = curr.next
    
    if curr.next:
        curr.next = curr.next.next
        self.size -= 1
    else:
        raise ValueError("Value not found")

def reverse_iterative(self) -> None:
    """
    Time Complexity: O(n)
    Space Complexity: O(1)
    """
    prev = None
    curr = self.head
    
    while curr:
        next_temp = curr.next
        curr.next = prev
        prev = curr
        curr = next_temp
    
    self.head = prev

def reverse_recursive(self) -> None:
    """
    Time Complexity: O(n)
    Space Complexity: O(n) due to recursion stack
    """
    def reverse_helper(curr, prev):
        if not curr:
            return prev
        next_temp = curr.next
        curr.next = prev
        return reverse_helper(next_temp, curr)
    
    self.head = reverse_helper(self.head, None)

def reverse_between(self, left: int, right: int) -> None:
    """
    Reverse a portion of the linked list
    Time Complexity: O(n)
    """
    if not self.head or left >= right:
        return
    
    dummy = ListNode(0)
    dummy.next = self.head
    prev = dummy
    
    for _ in range(left - 1):
        prev = prev.next
    
    curr = prev.next
    for _ in range(right - left):
        next_temp = curr.next
        curr.next = next_temp.next
        next_temp.next = prev.next
        prev.next = next_temp
    
    self.head = dummy.next

def has_cycle(self) -> bool:
    """
    Floyd's Cycle Detection
    Time Complexity: O(n)
    Space Complexity: O(1)
    """
    if not self.head:
        return False
    
    slow = fast = self.head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    
    return False

def find_cycle_start(self) -> ListNode:
    """
    Find start of cycle if exists
    Time Complexity: O(n)
    """
    if not self.head:
        return None
    
    # Find meeting point
    slow = fast = self.head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    else:
        return None
    
    # Find cycle start
    slow = self.head
    while slow != fast:
        slow = slow.next
        fast = fast.next
    
    return slow

def remove_cycle(self) -> None:
    """
    Remove cycle if exists
    Time Complexity: O(n)
    """
    if not self.head:
        return
    
    # Find meeting point
    slow = fast = self.head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    else:
        return
    
    # Find cycle start
    slow = self.head
    while slow.next != fast.next:
        slow = slow.next
        fast = fast.next
    
    # Remove cycle
    fast.next = None

def merge_sorted_lists(list1: ListNode, list2: ListNode) -> ListNode:
    """
    Merge two sorted linked lists
    Time Complexity: O(n + m)
    """
    dummy = ListNode(0)
    curr = dummy
    
    while list1 and list2:
        if list1.val <= list2.val:
            curr.next = list1
            list1 = list1.next
        else:
            curr.next = list2
            list2 = list2.next
        curr = curr.next
    
    curr.next = list1 or list2
    return dummy.next

def merge_k_sorted_lists(lists: list[ListNode]) -> ListNode:
    """
    Merge k sorted linked lists using divide and conquer
    Time Complexity: O(N log k) where N is total nodes
    """
    if not lists:
        return None
    
    def merge_two_lists(l1: ListNode, l2: ListNode) -> ListNode:
        dummy = ListNode(0)
        curr = dummy
        
        while l1 and l2:
            if l1.val <= l2.val:
                curr.next = l1
                l1 = l1.next
            else:
                curr.next = l2
                l2 = l2.next
            curr = curr.next
        
        curr.next = l1 or l2
        return dummy.next
    
    def merge_helper(start: int, end: int) -> ListNode:
        if start == end:
            return lists[start]
        if start + 1 == end:
            return merge_two_lists(lists[start], lists[end])
        
        mid = (start + end) // 2
        l1 = merge_helper(start, mid)
        l2 = merge_helper(mid + 1, end)
        return merge_two_lists(l1, l2)
    
    return merge_helper(0, len(lists) - 1)

def get_middle_node(self) -> ListNode:
    """
    Find middle node using slow-fast pointers
    Time Complexity: O(n)
    """
    if not self.head:
        return None
    
    slow = fast = self.head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    
    return slow

def get_nth_from_end(self, n: int) -> ListNode:
    """
    Find nth node from end
    Time Complexity: O(n)
    """
    if not self.head or n < 1:
        return None
    
    fast = slow = self.head
    
    # Move fast n steps ahead
    for _ in range(n):
        if not fast:
            return None
        fast = fast.next
    
    # Move both pointers until fast reaches end
    while fast:
        slow = slow.next
        fast = fast.next
    
    return slow

def is_palindrome(self) -> bool:
    """
    Check if linked list is palindrome
    Time Complexity: O(n)
    Space Complexity: O(1)
    """
    if not self.head or not self.head.next:
        return True
    
    # Find middle using slow-fast pointer
    slow = fast = self.head
    prev = None
    
    while fast and fast.next:
        fast = fast.next.next
        next_temp = slow.next
        slow.next = prev
        prev = slow
        slow = next_temp
    
    # If length is odd, skip middle element
    if fast:
        slow = slow.next
    
    # Compare first and second halves
    while prev and slow:
        if prev.val != slow.val:
            return False
        prev = prev.next
        slow = slow.next
    
    return True