কনটেন্টে যান

001 — Reverse Linked List

Problem link ও উৎস

  • Original source: Classic linked list exercise
  • Platform: LeetCode — https://leetcode.com/problems/reverse-linked-list/
  • Topic: linked list
  • Difficulty: Easy
  • Pattern: in-place reversal (pointer rewiring)
  • Basic idea inherited from: insert-at-head বারবার করা; node-to-node pointer ঘোরানো

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

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

একটা singly linked list দেওয়া আছে — মানে কতগুলো node, প্রতিটা পরেরটার দিকে একটা arrow (next) দিয়ে তাকিয়ে আছে। তোমার কাজ: সব arrow উল্টে দাও, যাতে শেষ node টা প্রথম হয়ে যায় আর প্রথমটা শেষ। নতুন head return করো।

উদাহরণ
আগে : 1 -> 2 -> 3 -> 4 -> 5 -> None
পরে : 5 -> 4 -> 3 -> 2 -> 1 -> None

Input ও output

উদাহরণ
Input : 1 -> 2 -> 3 -> 4 -> 5
Output: 5 -> 4 -> 3 -> 2 -> 1

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

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

একটা ট্রেনের বগি ভাবো, প্রতিটা সামনের বগির সাথে যুক্ত। তুমি চাও পুরো ট্রেন উল্টো দিকে চলুক। তুমি এক এক করে প্রতিটা সংযোগ খুলে উল্টো দিকে জুড়ছ — কিন্তু খোলার আগে পরের বগিটা কোথায় তা মনে রাখতে হবে, নাহলে বাকি ট্রেন হারিয়ে যাবে। সেই "মনে রাখা" = nxt pointer।

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

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

মূল ভিত হলো এক জোড়া node-এর মধ্যেকার arrow ঘোরানো। তুমি যদি জানো কীভাবে a -> b কে a <- b বানাতে হয়, তাহলে পুরো list টা just সেই কাজটা বারবার করা। সাথে "insert-at-head" চিন্তা — প্রতিটা node কে নতুন list-এর সামনে এনে বসানো।

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

লুকানো logic একটা invariant: যেকোনো মুহূর্তে prev হলো এ পর্যন্ত উল্টে ফেলা অংশের head, আর cur হলো এখনো-না-ছোঁয়া অংশের head। প্রতি step-এ আমরা একটা node কে উল্টানো অংশে যোগ করি, এই invariant ধরে রেখে। Loop শেষ হলে prev-ই পুরো উল্টানো list-এর head।

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

কোনো extra data structure লাগে না — শুধু তিনটা pointer (prev, cur, nxt)। এটাই এর সৌন্দর্য: O(1) extra space।

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

Linked list-এ node গুলো memory-তে ছড়িয়ে থাকে, শুধু next arrow দিয়ে বাঁধা। তাই array-র মতো index করা যায় না, কিন্তু arrow নিজে বদলানো যায় সহজে। তিনটা pointer দিয়ে আমরা link গুলো এক এক করে নিরাপদে ঘুরিয়ে দিতে পারি — কোনো node না হারিয়ে।

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

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

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

উদাহরণ
1) list -> [1,2,3,4,5]
2) উল্টাও -> [5,4,3,2,1]
3) নতুন list বানাও

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

এটা কাজ করে, কিন্তু O(n) extra space নেয় (array + নতুন node গুলো)। Interview-তে আসল চ্যালেঞ্জ হলো জায়গা নষ্ট না করে, in-place (O(1) space) উল্টানো। তাছাড়া নতুন node বানানো অপচয় — পুরোনো node গুলোর arrow ঘোরালেই তো হয়।

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

মূল observation: পুরো list একসাথে উল্টানোর দরকার নেই — শুধু প্রতিটা node-এর next কে তার আগের node-এর দিকে ঘুরিয়ে দিলেই হয়। শুধু খেয়াল রাখতে হবে, arrow ঘোরানোর আগে পরের node-টা হারিয়ে না ফেলি।

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

তিনটা pointer নিয়ে list-এর উপর একবার হাঁটো। প্রতি ধাপে: পরের node মনে রাখো (nxt), এখনকার node-এর arrow পিছনে ঘোরাও (cur.next = prev), তারপর prev আর cur কে এক ঘর এগিয়ে দাও। একবার পাস শেষ — list উল্টে গেছে।

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

মোচড়: "list উল্টাব" ভাবার বদলে ভাবো "প্রতিটা arrow আলাদা করে পিছনে ঘোরাব, আর হারানো ঠেকাতে পরেরটা আগে ধরে রাখব।" বড় কাজটা একটা ছোট, repeatable step-এ ভেঙে যায়।

ছবিতে বোঝা

prev, cur, nxt তিনজনের নাচ। 1 -> 2 -> 3 দিয়ে দেখি:

উদাহরণ
শুরু:    prev=None   cur=1 -> 2 -> 3 -> None

step 1:  nxt = 2 (মনে রাখলাম)
         1.next = None        (arrow উল্টালো)
         prev=1, cur=2
         অবস্থা: None <- 1     2 -> 3 -> None

step 2:  nxt = 3
         2.next = 1
         prev=2, cur=3
         অবস্থা: None <- 1 <- 2     3 -> None

step 3:  nxt = None
         3.next = 2
         prev=3, cur=None
         অবস্থা: None <- 1 <- 2 <- 3

cur = None → থামো। নতুন head = prev = 3

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

Input 1 -> 2 -> 3:

  1. শুরু: prev=None, cur=1
  2. nxt=2; 1.next=None; prev=1, cur=2 → উল্টানো অংশ: 1
  3. nxt=3; 2.next=1; prev=2, cur=3 → উল্টানো অংশ: 2 -> 1
  4. nxt=None; 3.next=2; prev=3, cur=None → উল্টানো অংশ: 3 -> 2 -> 1
  5. cur=None → loop শেষ। return prev = 3

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

Python

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

def reverse_list(head):
    prev = None
    cur = head
    while cur:
        nxt = cur.next      # পরেরটা আগে ধরে রাখো (নাহলে হারাবে)
        cur.next = prev     # arrow পিছনে ঘোরাও
        prev = cur          # prev এক ঘর এগোলো
        cur = nxt           # cur এক ঘর এগোলো
    return prev             # নতুন 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(reverse_list(build([1, 2, 3, 4, 5]))) == [5, 4, 3, 2, 1]
assert to_list(reverse_list(build([]))) == []        # খালি list
assert to_list(reverse_list(build([7]))) == [7]      # একটা node
print("সব test pass!")

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

  • prev = None — শুরুতে উল্টানো অংশ খালি, তাই এর head None।
  • cur = head — না-ছোঁয়া অংশ শুরু হয় আসল head থেকে।
  • while cur: — যতক্ষণ ছোঁয়ার মতো node আছে।
  • nxt = cur.next — arrow ঘোরানোর আগে পরের node বাঁচিয়ে রাখো।
  • cur.next = prev — এই node-এর arrow পিছনে (উল্টানো অংশের দিকে) ঘোরাও।
  • prev = cur / cur = nxt — দুজনেই এক ঘর সামনে।
  • return prev — loop শেষে prev পুরো উল্টানো list-এর head।

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

build([1,2,3,4,5]) বানায় 1->2->3->4->5। reverse_list সেটাকে 5->4->3->2->1 করে, to_list সেটাকে [5,4,3,2,1] বানায় — assert pass। খালি ও একক-node case-ও pass। শেষে print: সব 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; }
}
// ---- array <-> list helper (test চালাতে) ----
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 reverseList(head) {
  let prev = null, cur = head;
  while (cur) {
    const nxt = cur.next;    // পরেরটা আগে ধরে রাখো (নাহলে হারাবে)
    cur.next = prev;         // arrow পিছনে ঘোরাও
    prev = cur;              // prev এক ঘর এগোলো
    cur = nxt;               // cur এক ঘর এগোলো
  }
  return prev;               // নতুন head
}

// ---- test cases ----
const eq = (a, b) => JSON.stringify(a) === JSON.stringify(b);
assert(eq(listToArray(reverseList(arrayToList([1, 2, 3, 4, 5]))), [5, 4, 3, 2, 1]), "main");
assert(eq(listToArray(reverseList(arrayToList([]))), []), "খালি list");
assert(eq(listToArray(reverseList(arrayToList([7]))), [7]), "একটা node");
console.log("সব JS test pass!");

JS টীকা: linked list-এর কোনো built-in নেই, তাই ছোট একটা ListNode class আর arrayToList/listToArray converter দিয়ে test চালাই। মূল trick একই — তিনটা pointer (prev, cur, nxt), আর const nxt = cur.next রাখতেই হবে cur.next = prev করার আগে, নাহলে বাকি list হারিয়ে যায়। let দিয়ে reassignable pointer, const nxt দিয়ে প্রতি iteration-এর temporary।

TypeScript ও test cases

TypeScript
interface ListNode { val: number; next: ListNode | null }
const node = (val: number, next: ListNode | null = null): ListNode => ({ val, next });

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

function reverseList(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null;
  let cur: ListNode | null = head;
  while (cur) {
    const nxt: ListNode | null = cur.next;
    cur.next = prev;
    prev = cur;
    cur = nxt;
  }
  return prev;
}

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

TS টীকা: interface ListNode { val: number; next: ListNode | null } দিয়ে node-এর আকৃতি বাঁধা — next হয় আরেকটা node, নয় null। cur ও prev-কে ListNode | null টাইপ করায় কম্পাইলার জোর করে while (cur) null-check করায়, তাই cur.next-এ কখনো null-dereference হবে না। এই union type-ই linked-list bug-এর সবচেয়ে বড় রক্ষাকবচ।

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

সময়

O(n) — প্রতিটা node ঠিক একবার করে visit হয়, একবার করে arrow ঘোরে।

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

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

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

  • nxt = cur.next রাখার আগেই cur.next = prev করে ফেলা — তখন list-এর বাকি অংশ হারিয়ে যায়।
  • শেষে prev-এর বদলে cur return করা (cur তখন None)।
  • খালি list (head = None) আলাদা করে না ভাবা — যদিও এই code-এ loop চলেই না, তাই এমনিতেই ঠিক থাকে।

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

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

ভিত্তি: linked list traversal (একবার হেঁটে যাওয়া) + এক জোড়া node-এর arrow ঘোরানো। topic-এর ../implementation.py-তে reverse method আর ../visual-explanation.md-তে "reversal dance" frame দেখো।

পরের অনুশীলন

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

In-place pointer reversal: তিনটা pointer (prev, cur, nxt) নিয়ে এক পাসে link ঘোরানো — linked list-এর সবচেয়ে মৌলিক pattern, বহু কঠিন problem-এর building block।

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

ভবিষ্যতের আমাকে: "list উল্টানো = প্রতিটা arrow পিছনে ঘোরানো, পরেরটা আগে ধরে রেখে।" যখনই দেখবে কোনো problem-এ list/অংশ উল্টাতে হচ্ছে, এই তিন-pointer dance মনে করবে — এটা চোখ বন্ধ করে লিখতে পারা চাই।

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

  • Undo stack reversal: কোনো action-history list-কে উল্টো ক্রমে replay করতে in-place reversal কাজে লাগে।
  • Data packet/stream reordering: networking-এ buffered chunk-গুলোকে উল্টো ক্রমে process করার দরকার হলে।
  • Memory-constrained devices: embedded system-এ O(1) extra space-এ list উল্টানো জরুরি, কারণ extra array-র জায়গা নেই।
  • Bigger algorithms-এর building block: reverse-in-k-group, palindrome-check, reorder-list — সবেতেই এই তিন-pointer reversal core step।
  • Iterator/cursor rewind: singly-linked structure-এ পিছন দিকে হাঁটার দরকার হলে আগে অংশটা উল্টে নেওয়া হয়।

এক কথায়, যেখানেই pointer-based chain উল্টে দিতে হয় বা একটা list-কে উল্টো ক্রমে দরকার, এই O(1)-space in-place reversal-ই মৌলিক হাতিয়ার।

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