কনটেন্টে যান

015 — Reorder List

Problem link ও উৎস

  • 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

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

একটা 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 বদলাও।

Input ও 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

চেনা উদাহরণে বোঝা

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

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

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

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

ভেতরের যুক্তি

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

কী দিয়ে তথ্য রাখব

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

এটি কেন উপযুক্ত

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

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

সরল চিন্তা: সব 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

কোথায় বেশি কাজ হচ্ছে

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

যে বিষয়টি খেয়াল করতে হবে

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

আরও কম কাজে সমাধান

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

ভাবনার পরিবর্তন

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

ছবিতে বোঝা

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 (প্রথম অংশ থেকে একটি, দ্বিতীয় অংশ থেকে একটি):
  1 -> 5 -> 2 -> 4 -> 3

ছোট input-এ ধাপে ধাপে

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

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

কোড ও ব্যাখ্যা

Python

Python
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!")

কোডের প্রতিটি অংশ

  • 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: — দ্বিতীয় অর্ধ সবসময় সমান বা ছোট, তাই এটাকে শর্ত ধরলে ঠিক জায়গায় থামে।

Output মিলিয়ে দেখা

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!।

খরচ ও সাধারণ ভুল

সময়

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

অতিরিক্ত জায়গা

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

যে ভুলগুলো এড়াতে হবে

  • দুই অর্ধ আলাদা না করা (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 হারিয়ে যায়।

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

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

পরের অনুশীলন

কৌশলটি মনে রাখুন

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

নিজেকে যাচাই করুন

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

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