Skip to content

004 — Reverse Linked List (Iterative AND Recursive)

Source

  • Original source: Classic capstone interview problem (presented two ways in one sitting)
  • Platform: LeetCode — https://leetcode.com/problems/reverse-linked-list/
  • Topic: linked lists + recursion
  • Difficulty: Easy
  • Pattern: Pointer surgery — iterative three-pointer AND recursive rewiring
  • Basic idea inherited from: এটা একটা cross-topic capstone — এখানে মেশে 04 linked lists (node-এর next arrow ঘোরানো, pointer surgery) আর 06 recursion (একই কাজকে call stack দিয়ে করা: লেজ আগে উল্টাও, তারপর নিজের link ঠিক করো)। mock-এ এর শর্ত: এক বসায় দুই রূপই লেখা।

1. Problem in simple words

একটা singly linked list দেওয়া — কতগুলো node, প্রতিটা পরেরটার দিকে next arrow দিয়ে তাকিয়ে। সব arrow উল্টে দাও, যাতে শেষ node প্রথম হয়, প্রথমটা শেষ। নতুন head return করো। এই capstone-এ তোমাকে দুইভাবে করতে হবে — একবার iterative (লুপ), একবার recursive (call stack)।

আগে : 1 -> 2 -> 3 -> 4 -> 5 -> None
পরে : 5 -> 4 -> 3 -> 2 -> 1 -> None

2. Which basic idea does this inherit from?

এই problem দুটো আগের chapter-এর tool জোড়া দেয়:

  • 04 linked lists থেকে: এক জোড়া node-এর arrow ঘোরানো (a -> b কে a <- b), তিন pointer দিয়ে নিরাপদে link rewiring।
  • 06 recursion থেকে: একই কাজকে "আগে বাকি লেজটা উল্টাও (recursive call), তারপর শুধু এই node-এর link ঠিক করো" — base case + এক ধাপ + বিশ্বাস যে ছোট অংশ ঠিক হয়ে এসেছে।

iterative রূপ পুরোটা 04; recursive রূপ 04-এর arrow surgery-কে 06-এর call stack-এ বসায়। দুটো লেখাই এই combo চেনার drill।

3. What is the hidden math or logic?

লুকানো logic একটা invariant (iterative-এ) আর একটা induction (recursive-এ):

  • Iterative: prev সবসময় এ পর্যন্ত উল্টানো অংশের head, cur না-ছোঁয়া অংশের head। প্রতি step এই invariant ধরে রাখে।
  • Recursive: ধরে নাও reverse(head.next) লেজটা ঠিকঠাক উল্টে দিয়েছে; তখন শুধু head.next.next = head (পরের node-কে নিজের দিকে ফেরাও) আর head.next = None করলেই পুরো জিনিস উল্টে যায়। এটাই mathematical induction-এর "ছোট ক্ষেত্র ঠিক ⇒ বড় ক্ষেত্র ঠিক"।

4. Which data structure is needed?

কোনো extra data structure লাগে না।

  • Iterative: তিনটা pointer (prev, cur, nxt) — O(1) extra space।
  • Recursive: কোনো explicit structure নেই, কিন্তু call stack O(n) গভীর হয় (06 recursion-এর দাম)।

5. Why this data structure fits

Linked list-এ node গুলো memory-তে ছড়ানো, শুধু next arrow দিয়ে বাঁধা — তাই index না করে আমরা arrow নিজে বদলাই। iterative-এ তিন pointer দিয়ে link এক এক করে নিরাপদে ঘোরে, কোনো node না হারিয়ে। recursive-এ call stack নিজেই "পরের node কোথায়" মনে রেখে দেয়, তাই আলাদা nxt লাগে না — 06 recursion-এর সাথে এই কারণে খাপ খায়।

6. Real-life analogy

একটা ট্রেনের বগি ভাবো, প্রতিটা সামনের বগির সাথে যুক্ত, তুমি পুরো ট্রেন উল্টো দিকে চালাতে চাও।

  • Iterative = তুমি সামনে থেকে এক এক করে সংযোগ খুলে উল্টো দিকে জুড়ছ, খোলার আগে পরের বগি মনে রাখছ (nxt)।
  • Recursive = তুমি ভেতরে হেঁটে গিয়ে আগে শেষ বগিতে পৌঁছাও, তারপর ফেরার পথে প্রতিটা সংযোগ পেছনে জুড়তে জুড়তে আসো — call stack-ই তোমাকে ফেরার পথ মনে রাখায়।

7. Visual explanation

দুই রূপ পাশাপাশি, 1 -> 2 -> 3 দিয়ে:

ITERATIVE (prev, cur, nxt):
  শুরু:   prev=None  cur=1 -> 2 -> 3
  step1:  nxt=2; 1.next=None; prev=1, cur=2   => None<-1   2->3
  step2:  nxt=3; 2.next=1;   prev=2, cur=3   => None<-1<-2 3
  step3:  nxt=None; 3.next=2; prev=3, cur=None=> None<-1<-2<-3
  head = prev = 3

RECURSIVE (ভেতরে যাও, ফেরার পথে জোড়ো):
  reverse(1) -> reverse(2) -> reverse(3) -> reverse(None) base
  ফেরা: 3 head ধরে রাখলাম
        2.next.next = 2  (3->2);  2.next=None
        1.next.next = 1  (2->1);  1.next=None
  head = 3

8. Example input and 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

9. Brute force thinking

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

1) list -> [1,2,3,4,5]
2) উল্টাও -> [5,4,3,2,1]
3) নতুন list গড়ো

10. Why brute force is slow

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

11. Key observation

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

12. Optimized intuition

  • Iterative: তিন pointer নিয়ে একবার হাঁটো — পরেরটা মনে রাখো, এখনকার arrow পিছনে ঘোরাও, দুজনে এক ঘর এগোও।
  • Recursive: base case (খালি বা একক node) ফেরত দাও যেমন আছে; নাহলে আগে reverse(head.next) দিয়ে লেজ উল্টাও, তারপর head.next.next = head করে নিজের পরের node-কে নিজের দিকে ফেরাও, আর head.next = None দিয়ে পুরনো arrow কাটো।

13. Thinking tweak

মোচড়: "list উল্টাব" ভাবার বদলে ভাবো "প্রতিটা arrow আলাদা করে পিছনে ঘোরাব।" iterative-এ পরেরটা আগে ধরে রাখি; recursive-এ লেজটা আগে উল্টিয়ে নিই, তারপর শুধু একটা link ঠিক করি — call stack বাকি মনে রাখে।

14. Step-by-step dry run

Input 1 -> 2 -> 3 (iterative):

  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 → থামো; return prev = 3

15. Python solution

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

def reverse_iterative(head):
    prev = None
    cur = head
    while cur:
        nxt = cur.next      # পরেরটা আগে ধরে রাখো
        cur.next = prev     # arrow পিছনে ঘোরাও
        prev = cur          # prev এক ঘর এগোলো
        cur = nxt           # cur এক ঘর এগোলো
    return prev             # নতুন head

def reverse_recursive(head):
    if head is None or head.next is None:
        return head                 # base: খালি বা একক node নিজেই উল্টানো
    new_head = reverse_recursive(head.next)  # আগে লেজ উল্টাও
    head.next.next = head           # পরের node-কে নিজের দিকে ফেরাও
    head.next = None                # পুরনো arrow কাটো
    return new_head                 # নতুন head (সবচেয়ে শেষ node) উপরে পাঠাও

# ---- 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 (দুই রূপই একই উত্তর দিতে হবে) ----
for reverse in (reverse_iterative, reverse_recursive):
    assert to_list(reverse(build([1, 2, 3, 4, 5]))) == [5, 4, 3, 2, 1]
    assert to_list(reverse(build([]))) == []        # খালি list
    assert to_list(reverse(build([7]))) == [7]      # একটা node
    assert to_list(reverse(build([1, 2]))) == [2, 1] # দুই node
print("সব test pass!")

16. Line-by-line code explanation

Iterative:

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

Recursive:

  • if head is None or head.next is None: return head — base case: খালি বা শেষ node নিজেই নতুন head।
  • new_head = reverse_recursive(head.next) — বিশ্বাস করো লেজটা উল্টে এসেছে; new_head পুরো উল্টানো list-এর head।
  • head.next.next = head — এখন head.next হলো লেজের শেষ node; তার next-কে head-এর দিকে ফেরাও।
  • head.next = None — head-এর পুরনো forward arrow কেটে দাও (নাহলে cycle হবে)।
  • return new_head — অপরিবর্তিত head সব level-এ উপরে পাঠাও।

17. Output walkthrough

build([1,2,3,4,5]) দেয় 1->...->5। দুই রূপই 5->4->3->2->1 বানায়, to_list দেয় [5,4,3,2,1] — assert pass। for reverse in (...) লুপ দুই function-এই খালি/একক/জোড়া case চালায়, সবই pass। শেষে print: সব test pass!।

18. Time complexity

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

19. Space complexity

  • Iterative: O(1) — শুধু তিন pointer।
  • Recursive: O(n) — call stack list-এর গভীরতার সমান (06 recursion-এর hidden cost; খুব লম্বা list-এ stack overflow-র ঝুঁকি, তাই iterative-টা production-safe)।

20. Common mistakes

  • Iterative-এ nxt রাখার আগেই cur.next = prev করা — বাকি list হারায়।
  • Recursive-এ head.next = None ভুলে যাওয়া — পুরনো arrow থেকে যায়, ফলে শেষে cycle তৈরি হয়।
  • Recursive base case-এ শুধু head is None দেখা (head.next is None বাদ) — একক node-এ head.next.next crash করবে।
  • শেষে prev-এর বদলে cur return করা (iterative-এ cur তখন None)।

21. Which basic problem this inherits from

ভিত্তি: linked list traversal + এক জোড়া node-এর arrow ঘোরানো (04-এর ../../04-linked-lists/), আর "ছোট অংশ আগে সমাধান করে, ফেরার পথে নিজের কাজ" recursion (06-এর ../../06-recursion-and-backtracking/)। topic-03-এর 001-reverse-linked-list.md-ও দেখো — এটা তার দুই-রূপ সম্প্রসারণ।

22. Similar harder problems

23. Pattern learned

Pointer surgery, two ways: একই reversal-কে (a) তিন-pointer iterative loop, O(1) space আর (b) "লেজ আগে, link পরে" recursive, O(n) stack — দুইভাবে লেখা। iterative ↔ recursive এই অনুবাদটা বহু list/tree problem-এ লাগে।

24. Final summary

ভবিষ্যতের আমাকে: list উল্টানো = প্রতিটা arrow পিছনে ঘোরানো। iterative-এ "পরেরটা আগে ধরো"; recursive-এ "লেজ আগে উল্টাও, তারপর head.next.next = head; head.next = None"। interview-তে যেকোনো একটা চাইলে অন্যটাও বলে দাও — combo চেনার এটাই flex। দুটোই চোখ বন্ধ করে লিখতে পারা চাই।

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