কনটেন্টে যান

013 — Reverse Linked List II

Problem link ও উৎস

  • Original source: Classic linked list exercise
  • Platform: LeetCode — https://leetcode.com/problems/reverse-linked-list-ii/
  • Topic: linked list
  • Difficulty: Medium
  • Pattern: segmented reversal (head-insertion)
  • Basic idea inherited from: full reversal (problem 1) + সাবধানে boundary সেলাই

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

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

একটা linked list আর দুটো position left ও right (১ থেকে গোনা) দেওয়া। শুধু left থেকে right পর্যন্ত অংশটুকু উল্টে দাও, বাকিটা যেমন আছে তেমন থাকবে। এক পাসে করো। নতুন head return করো।

উদাহরণ
list : 1 -> 2 -> 3 -> 4 -> 5 ,  left = 2 , right = 4
শুধু 2..4 উল্টাও
ফল  : 1 -> 4 -> 3 -> 2 -> 5

Input ও output

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

Edge 1 (পুরোটা): 1 -> 2 -> 3 -> 4 -> 5 , left=1 , right=5 -> Output: 5 -> 4 -> 3 -> 2 -> 1
Edge 2 (এক node): 1 -> 2 -> 3 , left=2 , right=2  -> Output: 1 -> 2 -> 3 (কোনো বদল নেই)
Edge 3 (head ঘিরে): 3 -> 5 , left=1 , right=2     -> Output: 5 -> 3

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

একটা বইয়ের তাকের নির্দিষ্ট কয়েকটা বই উল্টো ক্রমে সাজাতে চাও। বাঁদিকের একটা স্থির বইকে খুঁটি ধরে, তার ঠিক ডানপাশের বইটা বারবার তুলে এনে খুঁটির পরে গুঁজে দাও — অংশটুকু উল্টে যায়, আশপাশের সাজানো বই অটুট থাকে।

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

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

এর ভিত্তি problem 1 ([001-reverse-linked-list.md](001-reverse-linked-list.md))-এর full reversal। সেখানে পুরো list উল্টানো হয়; এখানে শুধু একটা অংশ। নতুন চ্যালেঞ্জ: উল্টানো অংশের দুই প্রান্ত আবার সঠিকভাবে বাকি list-এর সাথে সেলাই (stitch) করা — না হলে list ভেঙে যায়।

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

লুকানো কৌশল head-insertion: left-এর ঠিক আগের node-কে (prev) একটা স্থির খুঁটি ধরে রাখো। তারপর অংশের ভেতরের প্রতিটা পরের node-কে এক এক করে তুলে এনে prev-এর ঠিক পরে বসাও। এতে ঠিক right − left বার এই "তুলে সামনে বসানো" করলে অংশটা উল্টে যায়, আর boundary দুটো আপনাআপনি ঠিক থাকে।

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

কোনো extra structure নয় — একটা dummy head (যদি left = 1 হয়ে head বদলায়) আর কয়েকটা pointer (prev, cur, nxt)। O(1) extra space।

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

Linked list-এ একটা node-কে অন্য জায়গায় সরানো মানে শুধু কয়েকটা arrow বদল — O(1), data সরানো লাগে না। head-insertion ঠিক এই সুবিধাটাই খাটায়: prev খুঁটি স্থির রেখে ভেতরের node গুলো সামনে এনে বসানো। dummy head থাকায় left = 1-এর special case আলাদা সামলাতে হয় না।

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

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

সরল চিন্তা: left..right অংশের value গুলো একটা array-তে নাও, array উল্টাও, তারপর সেই উল্টানো value গুলো আবার ওই অংশের node-এ বসিয়ে দাও।

উদাহরণ
2..4 অংশ = [2,3,4] -> উল্টাও -> [4,3,2] -> node গুলোতে বসাও
ফল: 1 -> 4 -> 3 -> 2 -> 5

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

value-copy করলে O(k) extra space লাগে (k = অংশের দৈর্ঘ্য), আর অনেক ক্ষেত্রে value নয়, node উল্টানোই উদ্দেশ্য। head-insertion দিয়ে কোনো array ছাড়াই, এক পাসে, পুরোনো node গুলোর arrow ঘুরিয়েই O(1) space-এ হয়ে যায়।

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

মূল observation: পুরো অংশ আলাদা করে উল্টে আবার জোড়ার দরকার নেই। left-এর আগের node-কে খুঁটি ধরে, ভেতরের পরের node-টা বারবার সামনে এনে বসালেই অংশটা উল্টে যায় — এবং দুই প্রান্তের সেলাই আপনাআপনি ঠিক থাকে।

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

dummy বসিয়ে prev কে left-এর ঠিক আগের node-এ নাও (left − 1 ঘর এগিয়ে)। cur = prev.next (অংশের প্রথম node, যেটা শেষে অংশের লেজ হবে)। তারপর right − left বার: cur-এর পরের node nxt-কে তুলে prev-এর পরে বসাও (cur.next = nxt.next, nxt.next = prev.next, prev.next = nxt)। শেষে dummy.next।

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

মোচড়: "অংশটা কেটে, উল্টে, আবার জুড়ব" না ভেবে ভাবো — "একটা খুঁটির পরে ভেতরের node গুলো এক এক করে সামনে এনে বসাই; ঠিক ততবার যতটা লম্বা অংশ।" তাহলে boundary সেলাই আর আলাদা করে ভাবতে হয় না।

ছবিতে বোঝা

prev খুঁটি, প্রতিবার cur-এর পরেরটা তুলে prev-এর পরে বসাও। 1->2->3->4->5, left=2, right=4:

উদাহরণ
dummy -> 1 -> 2 -> 3 -> 4 -> 5
prev = 1 (left-এর আগের node) , cur = 2

তুলে-সামনে-বসাও (right-left = 2 বার):
  nxt=3: 2->4, 3->2, 1->3  →  1 -> 3 -> 2 -> 4 -> 5
  nxt=4: 2->5, 4->3, 1->4  →  1 -> 4 -> 3 -> 2 -> 5

return dummy.next = 1 -> 4 -> 3 -> 2 -> 5

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

Input 1 -> 2 -> 3 -> 4 -> 5, left = 2, right = 4:

  1. dummy -> 1 -> 2 -> 3 -> 4 -> 5; prev = dummy
  2. left − 1 = 1 ঘর এগোও → prev = 1; cur = prev.next = 2
  3. বার ১: nxt = 3; cur.next = nxt.next (=4) → 2->4; nxt.next = prev.next (=2) → 3->2; prev.next = nxt (=3) → 1->3; এখন 1 -> 3 -> 2 -> 4 -> 5
  4. বার ২: nxt = 4; cur.next = nxt.next (=5) → 2->5; nxt.next = prev.next (=3) → 4->3; prev.next = nxt (=4) → 1->4; এখন 1 -> 4 -> 3 -> 2 -> 5
  5. right − left = 2 বার শেষ; return dummy.next = 1 -> 4 -> 3 -> 2 -> 5

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

Python

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

def reverse_between(head, left, right):
    dummy = ListNode(0, head)         # left=1 হলে head বদলায়, তাই dummy
    prev = dummy
    for _ in range(left - 1):         # prev কে left-এর ঠিক আগের node-এ নাও
        prev = prev.next
    cur = prev.next                   # অংশের প্রথম node (শেষে অংশের লেজ হবে)
    for _ in range(right - left):     # head-insertion ঠিক ততবার
        nxt = cur.next                # তুলে আনার node
        cur.next = nxt.next           # cur অংশের বাকি/পরের দিকে
        nxt.next = prev.next          # nxt অংশের বর্তমান মাথার আগে
        prev.next = nxt               # prev এখন nxt-কে মাথা ধরে
    return dummy.next

# ---- 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_between(build([1, 2, 3, 4, 5]), 2, 4)) == [1, 4, 3, 2, 5]
assert to_list(reverse_between(build([1, 2, 3, 4, 5]), 1, 5)) == [5, 4, 3, 2, 1]  # পুরোটা
assert to_list(reverse_between(build([1, 2, 3]), 2, 2)) == [1, 2, 3]              # এক node
assert to_list(reverse_between(build([3, 5]), 1, 2)) == [5, 3]                    # head ঘিরে
print("সব test pass!")

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

  • dummy = ListNode(0, head) — left = 1-এ head বদলালেও সহজে ফেরাতে।
  • for _ in range(left - 1): — prev কে left-এর ঠিক আগের node-এ নিয়ে যাও।
  • cur = prev.next — উল্টানো অংশের প্রথম node; এটাই শেষে অংশের লেজ।
  • for _ in range(right - left): — head-insertion ঠিক right − left বার।
  • nxt = cur.next — যে node-টা তুলে সামনে আনব।
  • cur.next = nxt.next — cur কে nxt-এর পরেরটার সাথে জোড়ো (লেজ হারায় না)।
  • nxt.next = prev.next — nxt কে অংশের বর্তমান মাথার আগে বসাও।
  • prev.next = nxt — prev এখন নতুন মাথা nxt-কে ধরে।
  • return dummy.next — আসল (সম্ভবত বদলানো) head।

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

build([1,2,3,4,5])-এ left=2,right=4 দিলে দুই বার head-insertion-এ [1,4,3,2,5]। left=1,right=5 হলে পুরোটা উল্টে [5,4,3,2,1]। left=right=2-তে শূন্য বার, কোনো বদল নেই। head ঘিরে [3,5],1,2 → [5,3]। সব assert pass → সব test pass!।

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

সময়

O(n) — prev-এ পৌঁছাতে রৈখিক, তারপর right − left বার head-insertion; মোট list-এর উপর এক পাস।

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

O(1) — শুধু dummy + কয়েকটা pointer; পুরোনো node reuse, extra memory বাড়ে না।

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

  • তিনটা arrow ভুল ক্রমে সেট করা — cur.next = nxt.next আগে না করলে অংশের পরের node হারায়।
  • prev কে left − 1-এর বদলে left ঘর এগিয়ে নেওয়া — তখন উল্টানো এক ঘর সরে যায়।
  • left = 1 (head বদলায়) case-এর জন্য dummy না নেওয়া।
  • loop চালানো right − left + 1 বার (এক বার বেশি) — boundary ভেঙে যায়; ঠিক right − left বার।

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

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

ভিত্তি: problem 1 ([001-reverse-linked-list.md](001-reverse-linked-list.md))-এর full reversal; তার উপর head-insertion + boundary সেলাই যোগ করে অংশ-উল্টানো। dummy head কৌশল problem 2 ([002-merge-two-sorted-lists.md](002-merge-two-sorted-lists.md)) থেকে।

পরের অনুশীলন

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

Segmented reversal via head-insertion: left-এর আগের node-কে খুঁটি ধরে ভেতরের পরের node বারবার সামনে এনে বসাও; right − left বার করলে অংশ উল্টে যায়, boundary আপনাআপনি ঠিক।

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

ভবিষ্যতের আমাকে: "অংশ উল্টাতে হলে — dummy নাও, prev কে left-এর আগে নাও, cur = prev.next; তারপর cur-এর পরেরটা right−left বার তুলে prev-এর পরে বসাও।" পুরো reversal-এর ছোট ভাই, শুধু খুঁটি আর গোনা ঠিক রাখো।

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