014 — Palindrome Linked List¶

Source¶

Original source: Classic linked list exercise
Platform: LeetCode — https://leetcode.com/problems/palindrome-linked-list/
Topic: linked list
Difficulty: Medium
Pattern: middle + reverse-half combo
Basic idea inherited from: problem 1 (reversal) আর problem 4 (middle) জোড়া লাগিয়ে

1. Problem in simple words¶

একটা linked list দেওয়া। এর value গুলো সামনে থেকে আর পিছন থেকে একই কি না বলো (palindrome) — যেমন 1 2 2 1 বা 1 2 3 2 1। আর শর্ত: O(1) extra space-এ করো। True/False return করো।

1 -> 2 -> 2 -> 1        palindrome  → True
1 -> 2 -> 3 -> 2 -> 1   palindrome  → True
1 -> 2                  নয়          → False

2. Which basic idea does this inherit from?¶

এটা দুটো আগের problem-এর combo। problem 4 (004-middle-of-list.md)-এর slow/fast দিয়ে মাঝ খোঁজা, আর problem 1 (001-reverse-linked-list.md)-এর in-place reversal দিয়ে দ্বিতীয় অর্ধেক উল্টানো। দুটো চেনা যন্ত্র জুড়ে দিলে নতুন problem-টা সহজ হয়ে যায়।

3. What is the hidden math or logic?¶

লুকানো logic: list palindrome হবে যদি এবং কেবল যদি তার প্রথম অর্ধেক, দ্বিতীয় অর্ধেকের উল্টোটার সমান হয়। তাই দ্বিতীয় অর্ধেক উল্টে নিয়ে দুই অর্ধেক পাশাপাশি মিলিয়ে দেখলেই হয়। বিজোড় দৈর্ঘ্যে মাঝের একক node-টা তুলনায় কোনো প্রভাব ফেলে না, তাই সেটা নিয়ে আলাদা ভাবতে হয় না।

4. Which data structure is needed?¶

কোনো নতুন structure নয় — শুধু pointer। slow/fast দিয়ে মাঝ, তারপর তিন-pointer reversal দিয়ে দ্বিতীয় অর্ধেক উল্টানো, শেষে দুই pointer দিয়ে তুলনা। সব O(1) space।

5. Why this data structure fits¶

সহজ পথ হলো সব value একটা list/array-তে নিয়ে দুই দিক থেকে মেলানো — কিন্তু সেটা O(n) space। linked list-এ আমরা একই node-এ দুই গতিতে হেঁটে মাঝ পাই, আর arrow ঘুরিয়ে in-place উল্টাই — তাই কোনো array ছাড়াই, শুধু pointer দিয়ে O(1) space-এ পুরো কাজ হয়।

6. Real-life analogy¶

একটা লম্বা ফিতের দুই মাথা মেলাতে চাও কিনা দেখতে — ফিতেটা ঠিক মাঝখানে ভাঁজ করে দুই অর্ধেক মুখোমুখি ধরো, তারপর শুরু থেকে এক এক করে মেলাও। ভাঁজ করা = মাঝ বের করে দ্বিতীয় অর্ধেক উল্টে নেওয়া; মেলানো = পাশাপাশি তুলনা।

7. Visual explanation¶

মাঝ বের করো → দ্বিতীয় অর্ধেক উল্টাও → দুই অর্ধেক মেলাও। 1->2->2->1:

মাঝ (slow/fast): slow থামে দ্বিতীয় অর্ধেকের শুরুতে (2য় 2)
    1 -> 2 -> [2 -> 1]

দ্বিতীয় অর্ধেক উল্টাও:
    প্রথম অর্ধেক: 1 -> 2
    উল্টানো দ্বিতীয়: 1 -> 2

মেলাও (left=head, right=উল্টানো মাথা):
    1 == 1 ✓
    2 == 2 ✓   → True

8. Example input and output¶

Input : 1 -> 2 -> 2 -> 1       -> Output: True   (জোড় দৈর্ঘ্য)
Input : 1 -> 2 -> 3 -> 2 -> 1  -> Output: True   (বিজোড়, মাঝ 3 উপেক্ষিত)
Input : 1 -> 2                 -> Output: False

Edge 1 (একটা node): 1   -> Output: True
Edge 2 (খালি list) : None -> Output: True

9. Brute force thinking¶

সরল চিন্তা: list ঘুরে সব value একটা array-তে নাও, তারপর array-টা তার উল্টোটার সমান কি না দেখো (দুই দিক থেকে দুই pointer মেলাও)।

1->2->2->1  =>  [1,2,2,1]
[1,2,2,1] == [1,2,2,1][::-1] ?  → True

10. Why brute force is slow¶

সময় O(n) ঠিকই, কিন্তু space O(n) — সব value array-তে রাখতে হয়। problem-এর আসল চ্যালেঞ্জ O(1) space। মাঝ + অর্ধেক-উল্টানো পদ্ধতি কোনো array ছাড়াই, শুধু pointer দিয়ে একই উত্তর দেয়।

11. Key observation¶

মূল observation: পুরো list মনে রাখার দরকার নেই। দ্বিতীয় অর্ধেক জায়গাতেই উল্টে নিলে, প্রথম অর্ধেকের সাথে পাশাপাশি মেলানো যায় — extra memory ছাড়াই।

12. Optimized intuition¶

খালি বা একক node হলে সরাসরি True। নাহলে slow/fast দিয়ে মাঝ বের করো (slow দ্বিতীয় অর্ধেকের শুরুতে থামে)। slow থেকে শুরু করে তিন-pointer reversal-এ দ্বিতীয় অর্ধেক উল্টাও। তারপর left = head, right = উল্টানো মাথা — right শেষ না হওয়া পর্যন্ত value মেলাও; কোথাও না মিললে False, নাহলে True।

13. Thinking tweak¶

মোচড়: "দুই দিক থেকে মেলাব কিন্তু পিছনে তো হাঁটা যায় না" — এই দেয়াল ভাঙো দ্বিতীয় অর্ধেক উল্টে দিয়ে। তখন "পিছন থেকে" হাঁটাটাই "সামনে থেকে" হয়ে যায়, আর দুই চেনা যন্ত্র (মাঝ + reversal) জুড়ে কাজ শেষ।

14. Step-by-step dry run¶

Input 1 -> 2 -> 2 -> 1:

খালি/একক নয় → এগোও
মাঝ: slow=1,fast=1 → slow=2(২য়),fast=2(৩য়) → fast.next.next = None থামো; slow = ৩য় node (মান 2)
দ্বিতীয় অর্ধেক (slow থেকে 2 -> 1) উল্টাও → 1 -> 2; মাথা prev = শেষ node (মান 1)
মেলাও: left = head (1), right = prev (1) → 1 == 1 ✓; left = 2, right = 2
2 == 2 ✓; right এর পরেরটা শেষ → loop শেষ
কোথাও mismatch হয়নি → return True

15. Python solution¶

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

def is_palindrome(head):
    if not head or not head.next:
        return True                  # খালি বা একক node — সবসময় palindrome

    slow = fast = head               # মাঝ খোঁজা (problem 4)
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    prev = None                      # দ্বিতীয় অর্ধেক উল্টানো (problem 1)
    cur = slow
    while cur:
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt

    left, right = head, prev          # দুই অর্ধেক মেলানো
    while right:                       # উল্টানো অর্ধেকটাই ছোট/সমান, তাই এটাই শর্ত
        if left.val != right.val:
            return False
        left = left.next
        right = right.next
    return True

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

# ---- tests ----
assert is_palindrome(build([1, 2, 2, 1])) is True       # জোড় palindrome
assert is_palindrome(build([1, 2, 3, 2, 1])) is True    # বিজোড় palindrome
assert is_palindrome(build([1, 2])) is False            # palindrome নয়
assert is_palindrome(build([1])) is True                # একক node
assert is_palindrome(build([])) is True                 # খালি
print("সব test pass!")

16. Line-by-line code explanation¶

if not head or not head.next: — খালি বা একক node সবসময় palindrome → সরাসরি True।
slow = fast = head ... while fast and fast.next: — slow/fast দিয়ে মাঝ; loop শেষে slow দ্বিতীয় অর্ধেকের শুরুতে।
prev = None; cur = slow; while cur: — তিন-pointer reversal-এ দ্বিতীয় অর্ধেক জায়গাতেই উল্টায়; prev উল্টানো অর্ধেকের মাথা।
left, right = head, prev — left সামনের অর্ধেক, right উল্টানো পিছনের অর্ধেক।
while right: — উল্টানো অর্ধেকটা প্রথম অর্ধেকের সমান/ছোট, তাই এটা শেষ হলেই থামা নিরাপদ।
if left.val != right.val: return False — কোথাও না মিললে palindrome নয়।
return True — পুরো মিলেছে।

17. Output walkthrough¶

build([1,2,2,1]): মাঝ পেয়ে দ্বিতীয় অর্ধেক 1->2 করে দুই অর্ধেক মেলে → True। [1,2,3,2,1]-এ মাঝের 3 উপেক্ষিত, বাকি মেলে → True। [1,2] মেলে না → False। একক ও খালি → True। সব assert pass → সব test pass!।

18. Time complexity¶

O(n) — মাঝ খোঁজা, অর্ধেক উল্টানো আর মেলানো — প্রতিটাই রৈখিক, মোট O(n)।

19. Space complexity¶

O(1) — কোনো array নয়, শুধু কয়েকটা pointer; দ্বিতীয় অর্ধেক জায়গাতেই উল্টানো হয়।

20. Common mistakes¶

দ্বিতীয় অর্ধেক উল্টানোর কথা ভুলে দুই দিক থেকে হাঁটতে চাওয়া — singly list-এ পিছনে হাঁটা যায় না।
তুলনার loop-এ while left and right-এর বদলে শুধু while left রাখা — বিজোড়ে মাঝ নিয়ে গন্ডগোল; while right রাখাই নিরাপদ।
খালি/একক node আলাদা করে না ধরা (যদিও এই code শুরুতেই সেটা সামলায়)।
value তুলনার সময় is ব্যবহার (left.val is right.val) — বড় সংখ্যায় ভুল হতে পারে; !=/== ব্যবহার করো।

21. Which basic problem this inherits from¶

ভিত্তি দুটো: problem 4 (004-middle-of-list.md)-এর slow/fast মাঝ-খোঁজা, আর problem 1 (001-reverse-linked-list.md)-এর in-place reversal। এই দুটো জুড়েই পুরো সমাধান।

22. Similar harder problems¶

Reorder List (মাঝ + reverse + merge) — https://leetcode.com/problems/reorder-list/ (এই tracker-এর #15)
Reverse Linked List (অর্ধেক উল্টানোর মূল) — https://leetcode.com/problems/reverse-linked-list/ (#1)
Middle of the Linked List (মাঝ-খোঁজার মূল) — https://leetcode.com/problems/middle-of-the-linked-list/ (#4)

23. Pattern learned¶

Middle + reverse-half combo: slow/fast দিয়ে মাঝ পাও, দ্বিতীয় অর্ধেক in-place উল্টাও, তারপর দুই অর্ধেক পাশাপাশি মেলাও — O(1) space-এ palindrome/reorder-জাতীয় সমস্যা।

24. Final summary¶

ভবিষ্যতের আমাকে: "list palindrome কিনা O(1) space-এ? array নিও না — মাঝ বের করো (slow/fast), দ্বিতীয় অর্ধেক উল্টাও, তারপর দুই মাথা থেকে মেলাও।" দুটো চেনা যন্ত্র (#1 + #4) জুড়লেই combo problem গলে যায়।

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;
};

function isPalindrome(head) {
  if (!head || !head.next) return true;     // খালি বা একক node — সবসময় palindrome

  let slow = head, fast = head;             // মাঝ খোঁজা (slow/fast)
  while (fast && fast.next) { slow = slow.next; fast = fast.next.next; }

  let prev = null, cur = slow;              // দ্বিতীয় অর্ধেক উল্টানো
  while (cur) { const nxt = cur.next; cur.next = prev; prev = cur; cur = nxt; }

  let left = head, right = prev;            // দুই অর্ধেক মেলানো
  while (right) {                            // উল্টানো অর্ধেকই ছোট/সমান
    if (left.val !== right.val) return false;
    left = left.next; right = right.next;
  }
  return true;
}

// ---- test cases ----
assert(isPalindrome(arrayToList([1, 2, 2, 1])) === true, "জোড় palindrome");
assert(isPalindrome(arrayToList([1, 2, 3, 2, 1])) === true, "বিজোড় palindrome");
assert(isPalindrome(arrayToList([1, 2])) === false, "palindrome নয়");
assert(isPalindrome(arrayToList([1])) === true, "একক node");
assert(isPalindrome(arrayToList([])) === true, "খালি");
console.log("সব JS test pass!");

JS টীকা: তিনটা চেনা step একসাথে — slow/fast দিয়ে মাঝ, তিন-pointer reversal দিয়ে দ্বিতীয় অর্ধেক উল্টানো, তারপর তুলনা — সব O(1) extra space-এ (array নেওয়া হয় না)। value তুলনায় !== ব্যবহার করো (!==/===), Object.is বা reference নয়। loop-শর্ত while (right) রাখাই নিরাপদ কারণ উল্টানো দ্বিতীয় অর্ধেক প্রথম অর্ধেকের সমান বা ছোট, তাই সেটা শেষ হলেই থামা ঠিক।

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;
};

function isPalindrome(head: ListNode | null): boolean {
  if (!head || !head.next) return true;

  let slow: ListNode = head;
  let fast: ListNode | null = head;
  while (fast && fast.next) { slow = slow.next!; fast = fast.next.next; }

  let prev: ListNode | null = null;
  let cur: ListNode | null = slow;
  while (cur) { const nxt: ListNode | null = cur.next; cur.next = prev; prev = cur; cur = nxt; }

  let left: ListNode | null = head;
  let right: ListNode | null = prev;
  while (right) {
    if (left!.val !== right.val) return false;
    left = left!.next; right = right.next;
  }
  return true;
}

function expect<T>(a: T, e: T, m = ""): void { if (a !== e) throw new Error(`FAIL ${m}`); }
expect(isPalindrome(arrayToList([1, 2, 2, 1])), true, "even");
expect(isPalindrome(arrayToList([1, 2, 3, 2, 1])), true, "odd");
expect(isPalindrome(arrayToList([1, 2])), false, "no");
expect(isPalindrome(arrayToList([1])), true, "single");
console.log("সব TS test pass!");

TS টীকা: তিনটা ভিন্ন pointer-role (slow/fast, prev/cur, left/right) আলাদা ListNode | null টাইপে থাকায় প্রতিটা stage-এ কম্পাইলার null-safety জোর করে। left! ও slow.next! assertion দিই যেখানে যুক্তিগতভাবে non-null কিন্তু কম্পাইলার প্রমাণ করতে পারে না (যেমন palindrome হলে left কখনো right-এর আগে শেষ হয় না)। union type-ই reversal-এর pointer-juggling-কে নিরাপদ রাখে।

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

Symmetry/integrity check: কোনো sequence সামনে-পিছনে একই কিনা (palindromic data, mirror pattern) যাচাই, মেমরি বাঁচিয়ে।
Bioinformatics: DNA-তে palindromic sequence (restriction site) খোঁজার মৌলিক চিন্তা।
Data validation: কিছু checksum/serial format-এ mirrored অংশ যাচাই করতে।
Audio/signal symmetry: sampled signal-এ mirror-symmetry detect করতে in-place reversal কৌশল।
Combo-pattern শেখা: "মাঝ বের করো + অর্ধেক উল্টাও" — reorder-list, fold-list-জাতীয় বহু problem-এর ভিত্তি।

এক কথায়, singly chain-এ O(1) space-এ "সামনে-পিছনে মেলানো" দরকার হলে — middle + reverse-half combo-ই আদর্শ, আর এটা দুটো মৌলিক pattern জোড়ার সুন্দর উদাহরণ।

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