৫টি সহজ Linked List কোডিং প্রবলেম ও সমাধান (Java)

Tree ও BFS/DFS-এর পর এবার Linked List — ইন্টারভিউয়ারদের প্রিয় জায়গা, কারণ এখানে pointer manipulation-এ সামান্য অসাবধানতাই ধরা পড়ে যায়। এই ৫টি প্রবলেমে Linked List-এর ৩টি মহাপ্যাটার্ন আছে: pointer reversal, fast/slow pointer, dummy node।

সব প্রবলেমে এই ListNode ক্লাসটি ব্যবহার হবে:

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

প্রবলেম ১: Reverse Linked List (LeetCode 206)

প্রশ্ন: একটি singly linked list উল্টে দিন। 1→2→3→4 হয়ে যাবে 4→3→2→1।

চিন্তার ধাপ: তিনটি pointer — prev, curr, আর next। প্রতি ধাপে: next-টা আগে বাঁচিয়ে রাখুন (নইলে বাকি list হারিয়ে যাবে!), তারপর curr-এর তীরটি পেছনে ঘুরিয়ে দিন, তারপর দুজনেই এক ঘর এগোন।

সমাধান:

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;

    while (curr != null) {
        ListNode next = curr.next;  // ১. বাকি list বাঁচিয়ে রাখুন
        curr.next = prev;           // ২. তীর উল্টে দিন
        prev = curr;                // ৩. prev এগোল
        curr = next;                // ৪. curr এগোল
    }
    return prev;  // curr এখন null, prev-ই নতুন head
}

Complexity: Time O(n), Space O(1)।

ইন্টারভিউ টিপ: এটি Linked List-এর "hello world" — চোখ বন্ধ করে লিখতে পারা চাই, কারণ এটি বহু কঠিন প্রবলেমের (Reverse in k-Groups, Palindrome check) ভেতরের যন্ত্রাংশ। Follow-up: "recursive version?" — লিখতে পারা ভালো, কিন্তু বলুন recursion-এ space O(n) হয়ে যায় (call stack), তাই iterative-ই উৎকৃষ্ট।

প্রবলেম ২: Middle of the Linked List (LeetCode 876)

প্রশ্ন: List-এর মাঝের node-টি রিটার্ন করুন। জোড় সংখ্যক node হলে দ্বিতীয় মাঝেরটি।

চিন্তার ধাপ: Fast/slow pointer (কচ্ছপ-খরগোশ) — slow এক ঘর করে চলে, fast দুই ঘর। Fast শেষে পৌঁছালে slow ঠিক মাঝখানে। এক pass-এই কাজ শেষ — length গুনে দ্বিতীয়বার হাঁটার দরকার নেই।

সমাধান:

public ListNode middleNode(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;

    while (fast != null && fast.next != null) {
        slow = slow.next;        // ১ ঘর
        fast = fast.next.next;   // ২ ঘর
    }
    return slow;
}

Complexity: Time O(n), Space O(1)।

ইন্টারভিউ টিপ: While-এর শর্তটি মুখস্থ করুন — fast != null && fast.next != null। ক্রমটি উল্টালে (আগে fast.next) জোড় দৈর্ঘ্যে NullPointerException। এই দুটি চেকের ক্রমই এই প্যাটার্নের সবচেয়ে common bug।

প্রবলেম ৩: Linked List Cycle (LeetCode 141)

প্রশ্ন: List-এ cycle আছে কিনা বের করুন (কোনো node-এর next যদি আগের কোনো node-কে দেখায়)।

চিন্তার ধাপ: আবার fast/slow — Floyd's cycle detection। Cycle থাকলে দৌড়ের ট্র্যাকের মতো: দ্রুত দৌড়বিদ ধীরটিকে একসময় ধরে ফেলবেই (প্রতি ধাপে ব্যবধান ১ করে কমে)। Cycle না থাকলে fast আগে null-এ পৌঁছে যাবে।

সমাধান:

public boolean hasCycle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;

    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;  // ধরা পড়েছে → cycle আছে
    }
    return false;  // fast শেষে পৌঁছেছে → cycle নেই
}

Complexity: Time O(n), Space O(1)।

ইন্টারভিউ টিপ: সহজ বিকল্প — HashSet-এ দেখা node রাখা — সেটাও বলুন, কিন্তু উল্লেখ করুন সেটি O(n) space; Floyd O(1)। নিশ্চিত follow-up: "cycle-টি কোথায় শুরু হয়েছে?" (LeetCode 142) — উত্তর: মিলনের পর একটি pointer head-এ ফিরিয়ে দিন, দুজনেই ১ ঘর করে চলুক — যেখানে আবার মিলবে সেটিই cycle-এর শুরু। এটুকু জানা থাকলেই ওই follow-up জেতা।

প্রবলেম ৪: Merge Two Sorted Lists (LeetCode 21)

প্রশ্ন: দুটি sorted linked list-কে একটি sorted list-এ মিশিয়ে দিন।

চিন্তার ধাপ: এখানে আসে তৃতীয় মহাপ্যাটার্ন — dummy node। নতুন list-এর head কে হবে তা নিয়ে বিশেষ case লেখার বদলে একটি dummy node দিয়ে শুরু করুন; শেষে dummy.next-ই উত্তর। তারপর দুই list-এর মাথা তুলনা করে ছোটটিকে জুড়তে থাকুন — merge sort-এর merge ধাপের মতোই।

সমাধান:

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(-1);  // head-এর special case দূর
    ListNode tail = dummy;

    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            tail.next = l1;
            l1 = l1.next;
        } else {
            tail.next = l2;
            l2 = l2.next;
        }
        tail = tail.next;
    }
    // একটি list শেষ, অন্যটির বাকি অংশ পুরোটা জুড়ে দিন
    tail.next = (l1 != null) ? l1 : l2;

    return dummy.next;
}

Complexity: Time O(m+n), Space O(1) — নতুন node তৈরি হয়নি, শুধু তীর ঘোরানো হয়েছে।

ইন্টারভিউ টিপ: শেষের tail.next = (l1 != null) ? l1 : l2; লাইনটি লক্ষ করুন — বাকি অংশ node-by-node কপি করার দরকার নেই, পুরো অবশিষ্ট list এক লাইনে জুড়ে যায়। Follow-up: "k টি sorted list হলে?" (LeetCode 23) → PriorityQueue অথবা divide & conquer, O(N log k)।

প্রবলেম ৫: Remove Nth Node From End (LeetCode 19)

প্রশ্ন: List-এর শেষ থেকে n-তম node-টি মুছে দিন — এক pass-এ।

চিন্তার ধাপ: দুটি pointer-এর মাঝে n ঘরের ব্যবধান তৈরি করুন: fast-কে আগে n ধাপ এগিয়ে দিন, তারপর দুজনে একসাথে চলুক। Fast শেষে পৌঁছালে slow থাকবে ঠিক মুছে-ফেলার-node-এর আগের ঘরে। আর head নিজেই মুছে যেতে পারে বলে — dummy node।

সমাধান:

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(-1);
    dummy.next = head;

    ListNode fast = dummy;
    ListNode slow = dummy;

    // fast-কে n+1 ধাপ এগিয়ে দিন (dummy থেকে), ব্যবধান তৈরি হলো
    for (int i = 0; i <= n; i++) {
        fast = fast.next;
    }

    // দুজনে একসাথে — fast null হলে slow টার্গেটের আগের node-এ
    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }

    slow.next = slow.next.next;  // মুছে ফেলা
    return dummy.next;
}

Complexity: Time O(n), Space O(1)।

ইন্টারভিউ টিপ: "কেন dummy?" — যদি [1,2,3] থেকে শেষ থেকে ৩য় (মানে head) মুছতে হয়, dummy ছাড়া আলাদা if লিখতে হতো। Head বদলে যেতে পারে এমন যেকোনো প্রবলেমে হাত অটোমেটিক dummy-তে যাওয়া চাই। আর "দুই pass-এ তো সহজ — length গুনে আবার হাঁটা" — সেটা বলে তারপর এক-pass সমাধান দিন; নিজে থেকে trade-off বলা senior signal।

৩টি মহাপ্যাটার্ন — মনে রাখুন

আর দুটি সোনার নিয়ম:

১. next আগে বাঁচান, পরে তীর ঘোরান — linked list bug-এর ৮০% হলো লিঙ্ক আগেই কেটে ফেলা। ২. কাগজে ৩-৪টি node এঁকে হাতে trace করুন — linked list মাথায় নয়, কাগজে সমাধান হয়। ইন্টারভিউতেও এঁকে দেখানো ভালো দেখায়।

পরবর্তী ধাপ: এগুলোর পর medium — Reorder List (143), Add Two Numbers (2), Palindrome Linked List (234 — মাঝ খোঁজা + reverse, অর্থাৎ প্রবলেম ১ ও ২-এর সংমিশ্রণ!), LRU Cache (146 — HashMap + doubly linked list, Staff loop-এর অতি প্রিয় প্রশ্ন)।