কনটেন্টে যান

014 — Palindrome Linked List

Problem link ও উৎস

  • 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) জোড়া লাগিয়ে

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

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

একটা 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

উদাহরণ
1->2->2->1  =>  [1,2,2,1]
[1,2,2,1] == [1,2,2,1][::-1] ?  → True

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

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

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

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

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

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

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

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

ছবিতে বোঝা

মাঝ বের করো → দ্বিতীয় অর্ধেক উল্টাও → দুই অর্ধেক মেলাও। 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

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

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

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

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

Python

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

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

  • 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 — পুরো মিলেছে।

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

build([1,2,2,1]): মাঝ পেয়ে দ্বিতীয় অর্ধেক 1->2 করে দুই অর্ধেক মেলে → True। [1,2,3,2,1]-এ মাঝের 3 উপেক্ষিত, বাকি মেলে → True। [1,2] মেলে না → False। একক ও খালি → True। সব 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;
};

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) রাখাই নিরাপদ কারণ উল্টানো দ্বিতীয় অর্ধেক প্রথম অর্ধেকের সমান বা ছোট, তাই সেটা শেষ হলেই থামা ঠিক।

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

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-কে নিরাপদ রাখে।

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

সময়

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

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

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

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

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

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

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

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

পরের অনুশীলন

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

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

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

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

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

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