🧩 4.6: Linked List Algoritmaları

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

def reverse_list(head):
    """
    Linked List'i Tersine Çevir - O(n) zaman, O(1) alan
    
    Mantık: 3 pointer kullan (prev, current, next_temp)
    Her adımda ok yönünü tersine çevir.
    """
    prev = None
    current = head
    
    print("🔄 Tersine çevirme başlıyor...\n")
    step = 0
    
    while current:
        step += 1
        next_temp = current.next  # Sonrakini kaydet
        current.next = prev       # Yönü tersine çevir
        
        print(f"Adım {step}: {current.val}.next = {prev.val if prev else 'None'}")
        
        prev = current            # prev ilerle
        current = next_temp       # current ilerle
    
    return prev  # Yeni head

# Test
def create_list(values):
    if not values: return None
    head = Node(values[0])
    current = head
    for val in values[1:]:
        current.next = Node(val)
        current = current.next
    return head

def print_list(head):
    result = []
    while head:
        result.append(str(head.val))
        head = head.next
    print(" → ".join(result) + " → NULL")

# Demo
head = create_list([1, 2, 3, 4, 5])
print("Önce: ", end="")
print_list(head)

new_head = reverse_list(head)
print("\nSonra: ", end="")
print_list(new_head)

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

def has_cycle(head):
    """
    Floyd's Cycle Detection - O(n) zaman, O(1) alan
    
    Tavşan-Kaplumbağa algoritması:
    - Slow: 1 adım
    - Fast: 2 adım
    - Eğer buluşurlarsa → DÖNGÜ VAR!
    """
    if not head or not head.next:
        return False
    
    slow = head  # 🐢 Kaplumbağa
    fast = head  # 🐰 Tavşan
    
    step = 0
    while fast and fast.next:
        step += 1
        slow = slow.next        # 1 adım
        fast = fast.next.next   # 2 adım
        
        print(f"Adım {step}: 🐢 slow={slow.val}, 🐰 fast={fast.val if fast else 'None'}")
        
        if slow == fast:
            print(f"\n🎯 BULUŞTULAR! Node {slow.val}'de döngü tespit edildi!")
            return True
    
    print("\n✅ Döngü yok!")
    return False

# Test 1: Döngü yok
print("=== TEST 1: Döngü olmayan liste ===")
head1 = Node(1)
head1.next = Node(2)
head1.next.next = Node(3)
has_cycle(head1)

# Test 2: Döngü var
print("\n=== TEST 2: Döngülü liste ===")
head2 = Node(1)
head2.next = Node(2)
head2.next.next = Node(3)
head2.next.next.next = Node(4)
head2.next.next.next.next = head2.next  # 4 → 2 (döngü!)
has_cycle(head2)

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

def find_middle(head):
    """
    Orta Noktayı Bul - O(n) zaman, O(1) alan
    
    Fast sona ulaştığında, slow ortada!
    """
    if not head:
        return None
    
    slow = head
    fast = head
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    
    return slow

# Test
def create_list(values):
    if not values: return None
    head = Node(values[0])
    current = head
    for val in values[1:]:
        current.next = Node(val)
        current = current.next
    return head

# Tek sayıda eleman
print("=== Tek sayı (5 eleman) ===")
head1 = create_list([1, 2, 3, 4, 5])
middle1 = find_middle(head1)
print(f"Liste: 1 → 2 → 3 → 4 → 5")
print(f"Orta: {middle1.val}")

# Çift sayıda eleman
print("\n=== Çift sayı (6 eleman) ===")
head2 = create_list([1, 2, 3, 4, 5, 6])
middle2 = find_middle(head2)
print(f"Liste: 1 → 2 → 3 → 4 → 5 → 6")
print(f"Orta: {middle2.val} (ikinci orta)")

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

def merge_sorted_lists(l1, l2):
    """
    İki Sıralı Listeyi Birleştir - O(n+m) zaman, O(1) alan
    """
    # Dummy head (işleri kolaylaştırır)
    dummy = Node(0)
    current = dummy
    
    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
    
    # Kalan elemanları ekle
    current.next = l1 if l1 else l2
    
    return dummy.next

# Test
def create_list(values):
    if not values: return None
    head = Node(values[0])
    current = head
    for val in values[1:]:
        current.next = Node(val)
        current = current.next
    return head

def print_list(head):
    result = []
    while head:
        result.append(str(head.val))
        head = head.next
    return " → ".join(result)

# Demo
l1 = create_list([1, 3, 5, 7])
l2 = create_list([2, 4, 6, 8])

print(f"Liste 1: {print_list(l1)}")
print(f"Liste 2: {print_list(l2)}")

merged = merge_sorted_lists(l1, l2)
print(f"\n🔀 Birleşik: {print_list(merged)}")