Skip to content

004 — Middle of the Linked List

Source

1. Problem in simple words

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

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

2. Which basic idea does this inherit from?

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

3. What is the hidden math or logic?

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

4. Which data structure is needed?

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

5. Why this data structure fits

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

6. Real-life analogy

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

7. Visual explanation

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  ← দ্বিতীয় মাঝ ✓

8. Example input and 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   (দ্বিতীয়টা)

9. Brute force thinking

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

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

10. Why brute force is slow

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

11. Key observation

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

12. Optimized intuition

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

13. Thinking tweak

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

14. Step-by-step dry run

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-এর দ্বিতীয়টা)

15. Python solution

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

16. Line-by-line code explanation

  • 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 মাঝে। জোড় দৈর্ঘ্যে শর্তের গঠনই দ্বিতীয় মাঝ দেয়।

17. Output walkthrough

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

18. Time complexity

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

19. Space complexity

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

20. Common mistakes

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

21. Which basic problem this inherits from

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

22. Similar harder problems

23. Pattern learned

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

24. Final summary

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

25. JavaScript solution (with test cases)

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-এ নিজে নিজে রান করে।

26. TypeScript solution (with test cases)

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 ফিরতে পারে।

27. কোথায় কাজে লাগে (real-world use)

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