015 — Reorder List¶

Source¶

Original source: Classic linked list exercise
Platform: LeetCode — https://leetcode.com/problems/reorder-list/
Topic: linked list
Difficulty: Medium
Pattern: middle + reverse + merge combo
Basic idea inherited from: problem 1 (reverse), 2 (merge), 4 (middle) — তিনটা মিলিয়ে triple combo

1. Problem in simple words¶

একটা singly linked list দেওয়া: L0 -> L1 -> L2 -> ... -> Ln-1 -> Ln। তোমাকে এটাকে ভাঁজ করে এই ক্রমে সাজাতে হবে:

আগে : L0 -> L1 -> L2 -> ... -> Ln-1 -> Ln
পরে : L0 -> Ln -> L1 -> Ln-1 -> L2 -> ...

মানে — প্রথমটা, তারপর শেষেরটা, তারপর দ্বিতীয়টা, তারপর শেষের-আগেরটা... এভাবে দুই প্রান্ত থেকে ভেতরের দিকে। তুমি কেবল node-এর arrow বদলাবে, value নয়। কিছু return করতে হয় না — list-টা in-place বদলাও।

2. Which basic idea does this inherit from?¶

এটা একদম খাঁটি combo problem — আগের তিনটা skeleton একসাথে জোড়া:

Middle খোঁজা (problem 4, 004-middle-of-list.md) — slow/fast দিয়ে list-টা দুই ভাগে কাটার জন্য।
Reverse (problem 1, 001-reverse-linked-list.md) — দ্বিতীয় অর্ধটা উল্টে দেওয়ার জন্য।
Merge (problem 2, 002-merge-two-sorted-lists.md) — দুই অর্ধ পালা করে গেঁথে দেওয়ার জন্য (এখানে value তুলনা নয়, শুধু পালা করে)।

নতুন কিছু শিখতে হয় না; শুধু পুরোনো তিনটা যন্ত্র সঠিক ক্রমে চালাতে হয়।

3. What is the hidden math or logic?¶

লুকানো logic হলো একটা symmetry: চূড়ান্ত ক্রমে i-তম position-এ বসে পালা করে সামনের আর পিছনের node। যদি দ্বিতীয় অর্ধটা উল্টে ফেলি, তাহলে "পিছন থেকে আসা" node গুলো এখন একটা সাধারণ forward list হয়ে যায় — তখন দুই অর্ধ শুধু পালা করে interleave করলেই কাঙ্ক্ষিত ভাঁজ পাওয়া যায়। অর্থাৎ "শেষ থেকে নাও" সমস্যাটা "reverse করে সামনে থেকে নাও"-তে বদলে যায়।

4. Which data structure is needed?¶

কোনো নতুন structure লাগে না — শুধু কয়েকটা pointer (slow, fast, prev, cur আর interleave করার সময় দুই অর্ধের head)। O(1) extra space-এই পুরো কাজ হয়।

5. Why this data structure fits¶

Linked list-এ আমরা index করে শেষ থেকে node তুলতে পারি না (array-র মতো L[n-i] নেই)। কিন্তু arrow ঘুরিয়ে দেওয়া সস্তা — O(1)। তাই দ্বিতীয় অর্ধ reverse করে "পিছনের node গুলো সামনে আনা"-র কাজটা pointer দিয়েই হয়ে যায়, extra array না বানিয়ে। এটাই linked list-এ O(1) space-এ ভাঁজ করার সঠিক উপায়।

6. Real-life analogy¶

একতাড়া কাগজ ভাবো, ১ থেকে n নম্বর দেওয়া। তুমি চাও পড়ার ক্রম হোক: প্রথম পাতা, শেষ পাতা, দ্বিতীয় পাতা, শেষের-আগের পাতা... সহজ উপায়: তাড়াটা মাঝ থেকে দুই ভাগ করো, পিছনের ভাগটা উল্টে হাতে নাও, তারপর দুই হাত থেকে পালা করে একটা একটা পাতা নতুন তাড়ায় রাখো। ঠিক সেটাই এখানে করছি।

7. Visual explanation¶

1 -> 2 -> 3 -> 4 -> 5 দিয়ে তিন ধাপ:

ধাপ ১ — middle-এ ভাঙো (slow শেষ first-half-এর):
  first  : 1 -> 2 -> 3
  second : 4 -> 5

ধাপ ২ — second অর্ধ reverse করো:
  first  : 1 -> 2 -> 3
  second : 5 -> 4

ধাপ ৩ — পালা করে interleave (first, second, first, second...):
  1 -> 5 -> 2 -> 4 -> 3

8. Example input and output¶

Input : 1 -> 2 -> 3 -> 4        -> Output: 1 -> 4 -> 2 -> 3
Input : 1 -> 2 -> 3 -> 4 -> 5   -> Output: 1 -> 5 -> 2 -> 4 -> 3

Edge 1 (একটা node):  1       -> Output: 1
Edge 2 (দুটো node):  1 -> 2  -> Output: 1 -> 2   (বদল নেই)
Edge 3 (খালি list):  None    -> Output: None

9. Brute force thinking¶

সরল চিন্তা: সব node-কে একটা array-তে রাখো (index করার সুবিধা পেতে)। তারপর দুই দিক থেকে দুটো index (i=0, j=n-1) নিয়ে পালা করে node তুলে নতুন arrow জোড়ো।

[1, 2, 3, 4, 5]
i=0 → 1, j=4 → 5, i=1 → 2, j=3 → 4, i=2 → 3 (মাঝ)
জোড়ো: 1 -> 5 -> 2 -> 4 -> 3

10. Why brute force is slow¶

কাজ করে, time-ও O(n), কিন্তু সব node-এর reference একটা array-তে রাখতে O(n) extra space লাগে। linked list-এর গোটা মজাই হলো arrow ঘুরিয়ে O(1) space-এ কাজ সারা। তাই array-তে সব তুলে ফেলা একরকম "linked list থাকার সুবিধা ফেলে দেওয়া"।

11. Key observation¶

মূল observation: "শেষ থেকে node তোলা" আসলে "দ্বিতীয় অর্ধ উল্টে সামনে থেকে তোলা"। একবার দ্বিতীয় অর্ধ reverse হয়ে গেলে, সমস্যা দাঁড়ায় দুটো সাধারণ forward list-কে পালা করে গাঁথা — যেটা আমরা merge-এর সময় থেকেই পারি।

12. Optimized intuition¶

তিন ধাপে ভাবো: (১) slow/fast দিয়ে middle খুঁজে list-টা দুই ভাগ করো, (২) দ্বিতীয় ভাগ reverse করো, (৩) দুই ভাগ থেকে পালা করে node নিয়ে arrow জোড়ো। প্রতিটা ধাপ একটা পরিচিত skeleton, আর প্রতিটাই O(n)/O(1)। মিলিয়ে এক পাসের মতো রৈখিক, কোনো extra array ছাড়াই।

13. Thinking tweak¶

মোচড়: "শেষ থেকে কীভাবে নেব" নিয়ে আটকে না থেকে list-টা মাঝখানে কেটে পিছনের অর্ধ উল্টে দাও — তখন কঠিন "শেষ থেকে তোলা" সমস্যাটা সহজ "দুটো forward list zip করা"-তে গলে যায়। বড় problem = তিনটা চেনা ছোট problem-এর সেলাই।

14. Step-by-step dry run¶

Input 1 -> 2 -> 3 -> 4:

Middle খোঁজো: slow=2, তাই first = 1 -> 2, second = 3 -> 4; slow.next=None দিয়ে কাটো।
second reverse করো → 4 -> 3।
Interleave শুরু: first=1, second=4। 1.next=4, 4.next=2 → 1 -> 4 -> 2 ...; এখন first=2, second=3।
2.next=3, 3.next=None → 1 -> 4 -> 2 -> 3; first=None, second=None।
second=None → থামো। ফল: 1 -> 4 -> 2 -> 3।

15. Python solution¶

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

def reorder_list(head):
    if not head or not head.next:
        return head

    # ১) middle খোঁজো — slow first-half-এর শেষে থামবে
    slow = fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    second = slow.next      # দ্বিতীয় অর্ধের শুরু
    slow.next = None        # দুই অর্ধ আলাদা করো

    # ২) দ্বিতীয় অর্ধ reverse করো
    prev = None
    cur = second
    while cur:
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt
    second = prev           # উল্টানো দ্বিতীয় অর্ধের নতুন head

    # ৩) দুই অর্ধ পালা করে interleave করো
    first = head
    while second:
        f_nxt = first.next
        s_nxt = second.next
        first.next = second     # first-এর পরে second-এর node
        second.next = f_nxt     # তার পরে first-এর পরের node
        first = f_nxt
        second = s_nxt
    return head

# ---- helpers (test-এর জন্য) ----
def build(values):
    dummy = ListNode()
    tail = dummy
    for v in values:
        tail.next = ListNode(v)
        tail = tail.next
    return dummy.next

def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out

# ---- tests ----
assert to_list(reorder_list(build([1, 2, 3, 4, 5]))) == [1, 5, 2, 4, 3]
assert to_list(reorder_list(build([1, 2, 3, 4]))) == [1, 4, 2, 3]
assert to_list(reorder_list(build([1]))) == [1]
assert to_list(reorder_list(build([1, 2]))) == [1, 2]
assert to_list(reorder_list(build([]))) == []
print("সব test pass!")

16. Line-by-line code explanation¶

if not head or not head.next: — খালি বা একক-node list-এ ভাঁজ করার কিছু নেই; যেমন আছে তেমন ফেরাও।
while fast.next and fast.next.next: — এই শর্তে slow ঠিক first-half-এর শেষ node-এ থামে, তাই slow.next থেকে দ্বিতীয় অর্ধ শুরু।
second = slow.next; slow.next = None — দুই অর্ধ আলাদা করো।
reverse-loop (prev/cur/nxt) — problem 1-এর সেই তিন-pointer dance, দ্বিতীয় অর্ধে চালানো।
interleave-loop — প্রতিবার দুই অর্ধের পরের node মনে রেখে (f_nxt, s_nxt) first→second→first ভাবে arrow জোড়া।
while second: — দ্বিতীয় অর্ধ সবসময় সমান বা ছোট, তাই এটাকে শর্ত ধরলে ঠিক জায়গায় থামে।

17. Output walkthrough¶

build([1,2,3,4,5]) → 1->2->3->4->5। Middle ভেঙে 1->2->3 ও 4->5; দ্বিতীয়টা reverse হয়ে 5->4; interleave করে 1->5->2->4->3, যা to_list-এ [1,5,2,4,3] — assert pass। জোড়-দৈর্ঘ্য, একক node, দুই node, খালি — সব pass হয়ে শেষে print: সব test pass!।

18. Time complexity¶

O(n) — middle খোঁজা, reverse, আর interleave প্রতিটাই list-এর উপর একবার করে হাঁটা; মোট রৈখিক।

19. Space complexity¶

O(1) — শুধু কয়েকটা pointer; কোনো array বা নতুন node নয়, পুরোনো node-গুলোরই arrow ঘোরে।

20. Common mistakes¶

দুই অর্ধ আলাদা না করা (slow.next = None ভুলে যাওয়া) — তখন interleave-এ cycle তৈরি হয়ে infinite loop।
Middle-এর শর্ত ভুল করা (while fast and fast.next বনাম while fast.next and fast.next.next) — first-half-এ ভুল node-এ থামলে জোড়/বিজোড়ে ভাঁজ এলোমেলো।
Interleave-এ পরের node আগে না রাখা (f_nxt, s_nxt) — arrow বদলানোর পরে বাকি list হারিয়ে যায়।

21. Which basic problem this inherits from¶

ভিত্তি তিনটা: middle খোঁজা (004-middle-of-list.md), reverse (001-reverse-linked-list.md), merge (002-merge-two-sorted-lists.md)। আটকে গেলে আগে এই তিনটা আলাদা করে ঝালিয়ে নাও — উত্তরের তিন-চতুর্থাংশ সেখানেই আছে।

22. Similar harder problems¶

Palindrome Linked List (middle + reverse-half combo) — https://leetcode.com/problems/palindrome-linked-list/ (এই tracker-এর #14)
Reverse Nodes in k-Group — https://leetcode.com/problems/reverse-nodes-in-k-group/ (#20)
Sort List (split + merge, recursively) — https://leetcode.com/problems/sort-list/ (#17)

23. Pattern learned¶

Combo: split-reverse-merge. কঠিন rearrange problem-কে চেনা ছোট skeleton (middle, reverse, merge) ভেঙে সেলাই করা — linked list-এর সবচেয়ে কাজের combo।

24. Final summary¶

ভবিষ্যতের আমাকে: "দুই প্রান্ত থেকে পালা করে সাজাতে হবে? list-টা মাঝে কাটো, পিছনের অর্ধ reverse করো, তারপর zip করো।" 'শেষ থেকে নেওয়া'-র গন্ধ পেলেই দ্বিতীয় অর্ধ উল্টানোর কথা মনে করবে।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।