# -*- coding: utf-8 -*-
"""
Singly Linked List — scratch থেকে বানানো, শেখার জন্য।

এখানে যা যা আছে:
  1. Node            — দুই-field-এর building block (value, next)।
  2. SinglyLinkedList — insert (head/tail/index), delete, search, reverse,
                        find_middle, has_cycle, প্লাস কিছু helper।
  3. merge_two_sorted — merge pattern-টা একটা standalone function হিসেবে।
  4. remove_nth_from_end — runner technique-টা একটা standalone function হিসেবে।

সবকিছু শুধু Python standard library ব্যবহার করে।
File-টা সরাসরি চালাও:  python implementation.py
Demo-র সব assert pass করতেই হবে।
"""


class Node:
    """Chain-এর একটা কড়া: একটা value প্লাস পরের কড়াটার ঠিকানা।"""

    def __init__(self, value):
        self.value = value
        self.next = None      # None মানে "chain-এর শেষ (এখন পর্যন্ত)"

    def __repr__(self):       # debugging সুন্দর হয়: Node(7)
        return f"Node({self.value})"


class SinglyLinkedList:
    """একটা head pointer আর একটা size counter সহ singly linked list।

    আমরা যে invariant গুলো maintain করি:
      * self._size সবসময় reachable node-এর সংখ্যার সমান।
      * শেষ reachable node-এর .next হলো None (কোনো accidental cycle না)।
    """

    def __init__(self):
        self.head = None
        self._size = 0

    def __len__(self):
        return self._size

    def is_empty(self):
        return self.head is None

    def to_list(self):
        """Value গুলো একটা Python list-এ জমা করো — test আর printing-এর জন্য। O(n)।"""
        out = []
        cur = self.head
        while cur is not None:
            out.append(cur.value)
            cur = cur.next
        return out

    # ------------------------------------------------------------------ #
    # Insertions
    # ------------------------------------------------------------------ #

    def insert_at_head(self, value):
        """O(1): নতুন node পুরনো chain-টা নিজের করে নেয়, তারপর head হয়ে যায়।"""
        new = Node(value)
        new.next = self.head      # আগে existing chain-টা ধরো
        self.head = new           # তারপর entry point সরাও
        self._size += 1

    def insert_at_tail(self, value):
        """এখানে O(n) কারণ আমরা কোনো tail pointer রাখি না (ইচ্ছে করেই
        simple রাখা)। শেষ node পর্যন্ত হাঁটো, তারপর নতুন node-টা ঝোলাও।"""
        new = Node(value)
        if self.head is None:     # খালি list: নতুন node-ই head
            self.head = new
        else:
            cur = self.head
            while cur.next is not None:
                cur = cur.next
            cur.next = new
        self._size += 1

    def insert_at_index(self, index, value):
        """O(n): predecessor পর্যন্ত হাঁটো, তারপর O(1) splice-টা করো।

        একটা dummy node ব্যবহার করে, যাতে index 0 (head insert)-এর
        কোনো special case না লাগে।
        """
        if not 0 <= index <= self._size:
            raise IndexError("index out of range")
        dummy = Node(None)
        dummy.next = self.head
        prev = dummy
        for _ in range(index):    # slot-এর আগের node-এ থামো
            prev = prev.next
        new = Node(value)
        new.next = prev.next      # 1) new আগে লেজটা ধরে
        prev.next = new           # 2) predecessor ছেড়ে দেয়
        self.head = dummy.next    # head বদলে থাকতে পারে (index == 0)
        self._size += 1

    # ------------------------------------------------------------------ #
    # Deletions / search
    # ------------------------------------------------------------------ #

    def delete_value(self, value):
        """`value` ধরে রাখা প্রথম node-টা delete করো। পেলে True return করে।

        Predecessor খুঁজতে O(n); bypass নিজে O(1)।
        Dummy node-এর কল্যাণে একই code head-ও delete করতে পারে।
        """
        dummy = Node(None)
        dummy.next = self.head
        prev = dummy
        while prev.next is not None:
            if prev.next.value == value:
                prev.next = prev.next.next    # bypass = delete
                self.head = dummy.next
                self._size -= 1
                return True
            prev = prev.next
        return False

    def find(self, value):
        """`value` ধরে রাখা প্রথম Node, অথবা None return করো। O(n)।"""
        cur = self.head
        while cur is not None:
            if cur.value == value:
                return cur
            cur = cur.next
        return None

    # ------------------------------------------------------------------ #
    # Interview-র classic গুলো
    # ------------------------------------------------------------------ #

    def reverse(self):
        """In place reverse করো। O(n) time, O(1) extra space।

        তিন-pointer-এর নাচ: prev = reversed zone, cur = untouched zone,
        nxt = lifeline যেটা arrow flip করার আগে বাকিটা save করে রাখে।
        """
        prev = None
        cur = self.head
        while cur is not None:
            nxt = cur.next        # 1) বাকিটা save করো
            cur.next = prev       # 2) এই node-এর arrow flip করো
            prev = cur            # 3) reversed zone বাড়ে
            cur = nxt             # 4) save করা অংশে পা দাও
        self.head = prev          # prev পুরনো শেষ node-এ গিয়ে শেষ হয়

    def find_middle(self):
        """Slow/fast pointer দিয়ে middle node। O(n) time, O(1) space।

        Even length-এ এটা দুটো middle node-এর মধ্যে SECOND-টা return করে
        (সাধারণ convention)।
        """
        slow = fast = self.head
        while fast is not None and fast.next is not None:
            slow = slow.next
            fast = fast.next.next
        return slow               # list খালি হলেই শুধু None

    def has_cycle(self):
        """Floyd's tortoise and hare। O(n) time, O(1) space।

        Cycle-এর ভেতরে hare প্রতি step-এ tortoise-এর উপর ঠিক একটা
        position এগিয়ে যায়, তাই cycle থাকলে তাদের একই node-এ
        নামতেই হবে। লক্ষ করো identity check (`is`), value equality না।
        """
        slow = fast = self.head
        while fast is not None and fast.next is not None:
            slow = slow.next
            fast = fast.next.next
            if slow is fast:
                return True
        return False


# ---------------------------------------------------------------------- #
# Standalone pattern functions (raw Node chain-এর উপর কাজ করে)
# ---------------------------------------------------------------------- #

def merge_two_sorted(h1, h2):
    """দুটো sorted node chain-কে একটা sorted chain-এ merge করো। O(n + m)।

    কোনো নতুন node বানানো হয় না — existing গুলোকেই re-thread করি।
    Merged chain-এর head return করে।
    """
    dummy = Node(None)
    tail = dummy
    while h1 is not None and h2 is not None:
        if h1.value <= h2.value:
            tail.next = h1        # ছোট সামনের node-টা link করো
            h1 = h1.next
        else:
            tail.next = h2
            h2 = h2.next
        tail = tail.next
    tail.next = h1 if h1 is not None else h2   # বাকি chain-টা জুড়ে দাও
    return dummy.next


def remove_nth_from_end(head, n):
    """শেষ থেকে nth node-টা এক pass-এ delete করো (runner technique)।

    front একটা dummy থেকে n + 1 hop-এর head start পায়; front শেষ থেকে
    পড়ে গেলে, back দাঁড়িয়ে থাকে target-এর PREDECESSOR-এ।
    (সম্ভবত নতুন) head return করে।
    """
    dummy = Node(None)
    dummy.next = head
    front = back = dummy
    for _ in range(n + 1):        # fixed gap-টা বানাও
        front = front.next
    while front is not None:      # দুজনকেই slide করাও; gap অটুট থাকে
        front = front.next
        back = back.next
    back.next = back.next.next    # target-টা bypass করো
    return dummy.next


def chain_from(values):
    """Helper: একটা Python list থেকে raw Node chain বানাও।"""
    dummy = Node(None)
    tail = dummy
    for v in values:
        tail.next = Node(v)
        tail = tail.next
    return dummy.next


def chain_to_list(head):
    """Helper: একটা raw Node chain-কে আবার Python list-এ পড়ে নাও।"""
    out = []
    while head is not None:
        out.append(head.value)
        head = head.next
    return out


# ---------------------------------------------------------------------- #
# Demo + tests
# ---------------------------------------------------------------------- #

if __name__ == "__main__":
    print("=== Build and edit a list ===")
    lst = SinglyLinkedList()
    assert lst.is_empty() and len(lst) == 0

    lst.insert_at_head(20)            # 20
    lst.insert_at_head(10)            # 10 -> 20
    lst.insert_at_tail(40)            # 10 -> 20 -> 40
    lst.insert_at_index(2, 30)        # 10 -> 20 -> 30 -> 40
    lst.insert_at_index(0, 5)         # 5 -> 10 -> 20 -> 30 -> 40
    print("after inserts:", lst.to_list())
    assert lst.to_list() == [5, 10, 20, 30, 40]
    assert len(lst) == 5

    assert lst.find(30) is not None and lst.find(30).value == 30
    assert lst.find(999) is None

    assert lst.delete_value(5) is True       # dummy দিয়ে head delete
    assert lst.delete_value(30) is True      # একটা middle node delete
    assert lst.delete_value(999) is False    # নেই এমন value
    print("after deletes:", lst.to_list())
    assert lst.to_list() == [10, 20, 40]
    assert len(lst) == 3

    print("\n=== Reverse in place ===")
    lst.reverse()
    print("reversed:", lst.to_list())
    assert lst.to_list() == [40, 20, 10]
    lst.reverse()                            # আবার উল্টে আগের মতো
    assert lst.to_list() == [10, 20, 40]

    empty = SinglyLinkedList()
    empty.reverse()                          # খালি list reverse: কোনো crash না
    assert empty.to_list() == []

    print("\n=== Middle and cycle ===")
    assert lst.find_middle().value == 20     # odd length: একদম মাঝখান
    lst.insert_at_tail(50)                   # 10 -> 20 -> 40 -> 50
    assert lst.find_middle().value == 40     # even length: second middle
    assert empty.find_middle() is None

    assert lst.has_cycle() is False
    # একটা ফেলনা chain-এ cycle বানিয়ে নিই: 1 -> 2 -> 3 -> (back to 2)
    looped = SinglyLinkedList()
    for v in [3, 2, 1]:
        looped.insert_at_head(v)             # 1 -> 2 -> 3
    n2 = looped.find(2)
    n3 = looped.find(3)
    n3.next = n2                             # loop-টা বন্ধ করো
    assert looped.has_cycle() is True

    print("\n=== Merge two sorted chains ===")
    merged = merge_two_sorted(chain_from([1, 3, 9]), chain_from([2, 4]))
    assert chain_to_list(merged) == [1, 2, 3, 4, 9]
    merged = merge_two_sorted(chain_from([]), chain_from([7]))
    assert chain_to_list(merged) == [7]
    merged = merge_two_sorted(chain_from([]), chain_from([]))
    assert chain_to_list(merged) == []

    print("=== Runner: remove nth from end ===")
    h = remove_nth_from_end(chain_from([1, 2, 3, 4, 5]), 2)
    assert chain_to_list(h) == [1, 2, 3, 5]
    h = remove_nth_from_end(chain_from([1, 2]), 2)   # head-টাই সরায়
    assert chain_to_list(h) == [2]
    h = remove_nth_from_end(chain_from([1]), 1)      # একটাই node
    assert chain_to_list(h) == []

    print("\nAll asserts passed. Pointers: tamed.")