কনটেন্টে যান

004 — Middle of the Linked List

Problem link ও উৎস

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

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

একটা singly linked list দেওয়া। তোমাকে এর মাঝের node-টা বের করতে হবে আর সেখান থেকে বাকি list return করতে হবে। list-এর দৈর্ঘ্য জোড় হলে দুটো মাঝ থাকে — তখন দ্বিতীয়টা নাও।

উদাহরণ
বিজোড় (5টা): 1 -> 2 -> 3 -> 4 -> 5      মাঝ = 3
জোড়  (6টা): 1 -> 2 -> 3 -> 4 -> 5 -> 6   মাঝ = 4 (দ্বিতীয়টা)

Input ও output

উদাহরণ
Input : 1 -> 2 -> 3 -> 4 -> 5        -> Output: 3 -> 4 -> 5     (head = node 3)
Input : 1 -> 2 -> 3 -> 4 -> 5 -> 6   -> Output: 4 -> 5 -> 6     (দ্বিতীয় মাঝ)

Edge 1 (একটা node): 1        -> Output: 1
Edge 2 (দুটো node): 1 -> 2   -> Output: 2   (দ্বিতীয়টা)

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

দুই বন্ধু একসাথে একটা লম্বা করিডোরের শুরু থেকে হাঁটা শুরু করল। একজন স্বাভাবিক গতিতে, আরেকজন ঠিক দ্বিগুণ জোরে। দ্রুতজন যখন করিডোরের শেষ দেয়ালে পৌঁছবে, ধীরজন তখন ঠিক মাঝখানে দাঁড়িয়ে থাকবে — মাপজোক ছাড়াই।

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

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

এটা সরাসরি problem 3 ([003-linked-list-cycle.md](003-linked-list-cycle.md))-এর slow/fast skeleton-এর উপর দাঁড়িয়ে। সেখানে আমরা শিখেছি দুটো pointer ভিন্ন গতিতে চালানো। এখানে cycle ধরা নয় — বরং সেই একই দুই-গতির খেলা দিয়ে এক পাসে মাঝ খুঁজে ফেলা। skeleton একই, শুধু লক্ষ্য আলাদা।

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

লুকানো অঙ্ক একটা সরল অনুপাত: fast যখন slow-এর দ্বিগুণ গতিতে এগোয়, তখন fast যখন শেষ ছুঁয়েছে, slow ঠিক অর্ধেক পথ গেছে। অর্ধেক পথ মানেই মাঝ। গণিতে — fast ২k ঘর গেলে slow k ঘর; fast শেষে (২k = n) মানে slow = n/2 = মাঝ।

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

কোনো extra data structure লাগে না — শুধু দুটো pointer (slow, fast)। O(1) extra space-এই কাজ হয়ে যায়।

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

Linked list-এ আমরা index করে সরাসরি মাঝে লাফ দিতে পারি না (length আগে থেকে জানা নেই)। কিন্তু একই list-এ দুই গতিতে হাঁটা যায়। দুই pointer-এর গতির অনুপাত নিজেই length মেপে দেয় — আলাদা করে আগে length গুনতে হয় না, এক পাসেই মাঝ পাওয়া যায়।

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

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

সরল চিন্তা: আগে পুরো list একবার ঘুরে length n গুনে নাও। তারপর আবার head থেকে শুরু করে n // 2 ঘর এগিয়ে গিয়ে সেই node return করো।

উদাহরণ
pass 1: 1->2->3->4->5 গুনে n = 5
pass 2: n//2 = 2 ঘর এগোও → node 3

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

এটা ঠিক উত্তর দেয়, কিন্তু list-এর উপর দুবার হাঁটে (একবার গুনতে, একবার পৌঁছাতে) — মোট ~2n কাজ। slow/fast দিয়ে একবারেই হয়ে যায়, কারণ গতির অনুপাত নিজেই গুনে রাখে। বড় list বা streaming data-তে এক-পাস সমাধানই কাম্য।

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

মূল observation: মাঝ খুঁজতে length জানার দরকার নেই। দুটো pointer-এর গতি ১:২ রাখলেই দ্রুতজন শেষে পৌঁছানোর মুহূর্তে ধীরজন আপনাআপনি মাঝে থাকে। গতির অনুপাতই length-এর কাজ করে দেয়।

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

slow আর fast দুটোকেই head থেকে ছাড়ো। প্রতি step-এ slow ১ ঘর, fast ২ ঘর। while fast and fast.next: শর্ত রাখো — মানে fast নিরাপদে দুই ঘর লাফাতে পারবে কিনা। loop শেষ হলে slow-ই মাঝ। জোড় দৈর্ঘ্যে এই শর্ত স্বয়ংক্রিয়ভাবে দ্বিতীয় মাঝ দেয়।

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

মোচড়: "length গুনে অর্ধেকে যাব" না ভেবে ভাবো — "একজনকে দ্বিগুণ জোরে ছেড়ে দিই; ও শেষে গেলে অন্যজন এমনিতেই মাঝে।" গোনা বাদ, গতি দিয়ে কাজ — এক পাসেই শেষ।

ছবিতে বোঝা

slow ১ ঘর, fast ২ ঘর। 1->2->3->4->5 (বিজোড়):

উদাহরণ
শুরু:     slow=1, fast=1
step 1:   slow=2, fast=3
step 2:   slow=3, fast=5
          fast.next = None → থামো
          slow = 3  ← মাঝ ✓

1->2->3->4->5->6 (জোড়):
step 1:   slow=2, fast=3
step 2:   slow=3, fast=5
step 3:   slow=4, fast=None   (5.next.next = None)
          fast = None → থামো
          slow = 4  ← দ্বিতীয় মাঝ ✓

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

Input 1 -> 2 -> 3 -> 4 (জোড়, ৪টা):

  1. শুরু: slow=1, fast=1
  2. fast ও fast.next আছে → slow=2, fast=3
  3. fast আছে, fast.next আছে → slow=3, fast=None (3.next.next = None)
  4. fast=None → loop শেষ
  5. return slow = 3 → অর্থাৎ 3 -> 4 (দুই মাঝ 2,3-এর দ্বিতীয়টা)

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

Python

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

def middle_node(head):
    slow = fast = head
    while fast and fast.next:     # fast দুই ঘর লাফাবে, তাই দুটোই থাকা চাই
        slow = slow.next          # ১ ঘর
        fast = fast.next.next     # ২ ঘর
    return slow                   # fast শেষে → slow ঠিক মাঝে

# ---- 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(middle_node(build([1, 2, 3, 4, 5]))) == [3, 4, 5]       # বিজোড় → আসল মাঝ
assert to_list(middle_node(build([1, 2, 3, 4, 5, 6]))) == [4, 5, 6]    # জোড় → দ্বিতীয় মাঝ
assert to_list(middle_node(build([1]))) == [1]                         # একটা node
assert to_list(middle_node(build([1, 2]))) == [2]                      # জোড় → দ্বিতীয়টা
print("সব test pass!")

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

  • slow = fast = head — দুজনেই head থেকে শুরু।
  • while fast and fast.next: — fast দুই ঘর লাফায়, তাই fast ও fast.next দুটোই থাকতে হবে; নাহলে শেষ ছুঁয়েছে।
  • slow = slow.next — ধীরজন ১ ঘর।
  • fast = fast.next.next — দ্রুতজন ২ ঘর।
  • return slow — loop শেষে fast শেষপ্রান্তে, তাই slow মাঝে। জোড় দৈর্ঘ্যে শর্তের গঠনই দ্বিতীয় মাঝ দেয়।

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

build([1,2,3,4,5]) বানায় 1->2->3->4->5; middle_node ফেরায় node 3, তাই to_list দেয় [3,4,5]। ৬-নোডের list-এ ফেরায় node 4 → [4,5,6]। একক node → [1]; দুই-নোডে দ্বিতীয়টা → [2]। সব assert pass → সব test pass!।

JavaScript ও test cases

JavaScript
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };

class ListNode {
  constructor(val = 0, next = null) { this.val = val; this.next = next; }
}
const arrayToList = (arr) => {
  const dummy = new ListNode();
  let tail = dummy;
  for (const v of arr) { tail.next = new ListNode(v); tail = tail.next; }
  return dummy.next;
};
const listToArray = (head) => {
  const out = [];
  while (head) { out.push(head.val); head = head.next; }
  return out;
};

function middleNode(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {   // fast দুই ঘর লাফাবে, তাই দুটোই থাকা চাই
    slow = slow.next;          // ১ ঘর
    fast = fast.next.next;     // ২ ঘর
  }
  return slow;                 // fast শেষে -> slow ঠিক মাঝে
}

// ---- test cases ----
const eq = (a, b) => JSON.stringify(a) === JSON.stringify(b);
assert(eq(listToArray(middleNode(arrayToList([1, 2, 3, 4, 5]))), [3, 4, 5]), "বিজোড় -> আসল মাঝ");
assert(eq(listToArray(middleNode(arrayToList([1, 2, 3, 4, 5, 6]))), [4, 5, 6]), "জোড় -> দ্বিতীয় মাঝ");
assert(eq(listToArray(middleNode(arrayToList([1]))), [1]), "একটা node");
assert(eq(listToArray(middleNode(arrayToList([1, 2]))), [2]), "জোড় -> দ্বিতীয়টা");
console.log("সব JS test pass!");

JS টীকা: while (fast && fast.next) শর্তটাই জোড়-দৈর্ঘ্যে দ্বিতীয় মাঝ দেয় — শর্ত বদলে শুধু while (fast.next && fast.next.next) করলে প্রথম মাঝ আসত। length আগে গুনে দুবার হাঁটার দরকার নেই; গতির অনুপাত ১:২ নিজেই length মেপে দেয়, তাই এক পাসেই মাঝ। arrayToList/listToArray helper দিয়ে snippet node-এ নিজে নিজে রান করে।

TypeScript ও test cases

TypeScript
interface ListNode { val: number; next: ListNode | null }
const arrayToList = (arr: number[]): ListNode | null => {
  let head: ListNode | null = null;
  for (let i = arr.length - 1; i >= 0; i--) head = { val: arr[i], next: head };
  return head;
};
const listToArray = (head: ListNode | null): number[] => {
  const out: number[] = [];
  while (head) { out.push(head.val); head = head.next; }
  return out;
};

function middleNode(head: ListNode | null): ListNode | null {
  let slow: ListNode | null = head;
  let fast: ListNode | null = head;
  while (fast && fast.next) {
    slow = slow!.next;        // fast থাকলে slow-ও থাকে
    fast = fast.next.next;
  }
  return slow;
}

function expect<T>(a: T, e: T, m = ""): void { if (a !== e) throw new Error(`FAIL ${m}`); }
const S = JSON.stringify;
expect(S(listToArray(middleNode(arrayToList([1, 2, 3, 4, 5])))), S([3, 4, 5]), "odd");
expect(S(listToArray(middleNode(arrayToList([1, 2, 3, 4, 5, 6])))), S([4, 5, 6]), "even");
expect(S(listToArray(middleNode(arrayToList([1])))), S([1]), "single");
expect(S(listToArray(middleNode(arrayToList([1, 2])))), S([2]), "two");
console.log("সব TS test pass!");

TS টীকা: ListNode | null union-এ while (fast && fast.next) দুই ধাপ narrow করে — তাই block-এর ভেতরে fast.next.next নিরাপদ। slow!.next-এ ! দিই কারণ যুক্তিগতভাবে slow fast-এর পিছনে, কিন্তু কম্পাইলার তা স্বাধীনভাবে প্রমাণ করতে পারে না। return type ListNode | null সততার সাথে বলে দেয় খালি list-এ null ফিরতে পারে।

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

সময়

O(n) — fast n/2 ধাপে শেষে পৌঁছায়, তাই মোট রৈখিক; list-এর উপর একবারই হাঁটা।

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

O(1) — শুধু দুটো pointer; list-এর সাইজের সাথে extra memory বাড়ে না।

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

  • while শর্তে শুধু fast চেক করা, fast.next না — তখন fast.next.next-এ crash।
  • জোড় দৈর্ঘ্যে প্রথম মাঝ চেয়ে শর্ত গুলিয়ে ফেলা; দ্বিতীয় মাঝ চাইলে while fast and fast.next: রাখতেই হবে।
  • length আগে গুনে দুবার হাঁটা — কাজ করে, কিন্তু এক-পাস সুবিধা হারায়।

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

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

ভিত্তি: problem 3-এর slow/fast skeleton ([003-linked-list-cycle.md](003-linked-list-cycle.md)) আর সাধারণ traversal (../operations.md)। দুই-speed চিন্তার ছবি ../visual-explanation.md-এর "tortoise–hare" frame-এ।

পরের অনুশীলন

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

Slow/fast pointers (middle finding): এক pointer ১ ঘর, আরেকটা ২ ঘর — দ্রুতজন শেষে গেলে ধীরজন মাঝে। length না গুনে এক পাসে মাঝ পাওয়ার classic কৌশল।

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

ভবিষ্যতের আমাকে: "মাঝ লাগবে? length গুনো না — slow ১ ঘর, fast ২ ঘর ছাড়ো; fast শেষে গেলে slow মাঝে।" জোড়ে দ্বিতীয় মাঝ চাইলে while fast and fast.next:। এই skeleton split-list, palindrome, reorder — সবেতেই ফিরে আসবে।

কোথায় কাজে লাগে

  • List splitting: merge sort বা reorder-list-এ list-কে দুই অর্ধে ভাগ করতে মাঝ লাগে — এই slow/fast দিয়ে এক পাসে।
  • Streaming median-ish: একবারে length না জেনেও মাঝ-উপাদান বের করা (যেখানে rewind কঠিন)।
  • Pagination/midpoint jump: doubly বা singly chain-এ "মাঝখানে যাও" দরকার হলে।
  • Palindrome / symmetry check: মাঝ বের করে দ্বিতীয় অর্ধেক উল্টে মেলানোর প্রথম ধাপ।
  • Load balancing on a chain: একটা linked pipeline-কে দুই সমান অংশে ভাগ করতে।

এক কথায়, "length না গুনে এক পাসে মাঝ চাই" — singly chain বা stream-এ — এই slow/fast runner-ই আদর্শ; আর এটা split/palindrome-জাতীয় বহু combo problem-এর প্রথম ইট।

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