ভূমিকা
Linked List হলো একটি linear data structure যেখানে প্রতিটি element (node) একটি value এবং পরবর্তী node-এর reference ধারণ করে। Array-এর মতো index নেই, তাই traversal করতে হয়। Interview-এ Linked List-এর সমস্যা খুবই common — Two Pointers, Fast & Slow Pointers, এবং Reversal technique দিয়ে বেশিরভাগ সমস্যা সমাধান করা যায়।
সমস্যা ১: Add Two Numbers
সমস্যার বিবরণ
দুটি non-empty linked list দেওয়া আছে যেগুলো দুটি non-negative integer represent করে। Digits গুলো reverse order-এ store করা আছে এবং প্রতিটি node-এ একটি digit আছে। দুটি সংখ্যার যোগফল একটি linked list হিসেবে return করতে হবে।
উদাহরণ
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
কারণ: 342 + 465 = 807 → reverse: [7,0,8]
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]
কারণ: 9999999 + 9999 = 10009998
চিন্তার পদ্ধতি
দুটি list একসাথে traverse করব। প্রতিটি step-এ দুটি digit এবং carry যোগ করব। যোগফলের ones digit নতুন node হবে, tens digit পরের step-এর carry হবে। দুটি list শেষ হলেও carry বাকি থাকলে নতুন node তৈরি করব।
সমাধান (Java)
public class AddTwoNumbers {
static class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; }
}
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0); // Dummy head node
ListNode current = dummy;
int carry = 0;
// দুটি list শেষ না হওয়া পর্যন্ত অথবা carry থাকা পর্যন্ত চলব
while (l1 != null || l2 != null || carry != 0) {
int sum = carry;
if (l1 != null) {
sum += l1.val;
l1 = l1.next;
}
if (l2 != null) {
sum += l2.val;
l2 = l2.next;
}
carry = sum / 10; // পরের step-এর carry
current.next = new ListNode(sum % 10); // Ones digit নতুন node
current = current.next;
}
return dummy.next;
}
private static String listToString(ListNode head) {
StringBuilder sb = new StringBuilder("[");
while (head != null) {
sb.append(head.val);
if (head.next != null) sb.append(",");
head = head.next;
}
return sb.append("]").toString();
}
public static void main(String[] args) {
AddTwoNumbers solution = new AddTwoNumbers();
// l1: 2→4→3 (342), l2: 5→6→4 (465)
ListNode l1 = new ListNode(2);
l1.next = new ListNode(4);
l1.next.next = new ListNode(3);
ListNode l2 = new ListNode(5);
l2.next = new ListNode(6);
l2.next.next = new ListNode(4);
System.out.println(listToString(solution.addTwoNumbers(l1, l2)));
// Output: [7,0,8]
}
}
সময় জটিলতা: O(max(m, n)) | স্থান জটিলতা: O(max(m, n))
সমস্যা ২: Remove Nth Node From End of List
সমস্যার বিবরণ
একটি linked list এবং একটি integer n দেওয়া আছে। List-এর শেষ থেকে n-তম node টি সরিয়ে দিয়ে updated list return করতে হবে।
উদাহরণ
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
কারণ: শেষ থেকে 2য় node হলো 4 → সরিয়ে দিই
Input: head = [1], n = 1
Output: []
Input: head = [1,2], n = 1
Output: [1]
চিন্তার পদ্ধতি
Two Pointer (Fast & Slow) technique ব্যবহার করব। Fast pointer-কে প্রথমে n+1 step এগিয়ে দেব। তারপর দুটো pointer একসাথে চলবে যতক্ষণ fast pointer list-এর শেষে পৌঁছায়। এই সময়ে slow pointer ঠিক target node-এর আগে থাকবে।
সমাধান (Java)
public class RemoveNthFromEnd {
static class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; }
}
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode fast = dummy;
ListNode slow = dummy;
// Fast pointer-কে n+1 step এগিয়ে দিই
for (int i = 0; i <= n; i++) {
fast = fast.next;
}
// Fast শেষে পৌঁছানো পর্যন্ত একসাথে চলি
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
// Slow এখন target-এর আগে আছে → target skip করি
slow.next = slow.next.next;
return dummy.next;
}
public static void main(String[] args) {
RemoveNthFromEnd solution = new RemoveNthFromEnd();
// List: 1→2→3→4→5, n=2
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);
ListNode result = solution.removeNthFromEnd(head, 2);
// Print result
while (result != null) {
System.out.print(result.val + " ");
result = result.next;
}
// Output: 1 2 3 5
}
}
সময় জটিলতা: O(n) | স্থান জটিলতা: O(1)
সমস্যা ৩: Linked List Cycle II
সমস্যার বিবরণ
একটি linked list দেওয়া আছে। যদি list-এ cycle থাকে, তাহলে cycle শুরু হওয়ার node টি return করতে হবে। Cycle না থাকলে null return করতে হবে।
উদাহরণ
Input: head = [3,2,0,-4], pos = 1
Output: Node with value 2
কারণ: -4 এর next হলো index 1 (value=2) → cycle শুরু 2 থেকে
Input: head = [1,2], pos = 0
Output: Node with value 1
Input: head = [1], pos = -1
Output: null (কোনো cycle নেই)
চিন্তার পদ্ধতি
Floyd's Cycle Detection Algorithm ব্যবহার করব। Fast (2 step) ও Slow (1 step) pointer দিয়ে প্রথমে meet point খুঁজব। Meet হলে slow pointer-কে head-এ পাঠাব। এবার দুটো pointer একই গতিতে চলবে — যেখানে মিলবে সেটাই cycle শুরুর node।
সমাধান (Java)
public class LinkedListCycleII {
static class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; }
}
public ListNode detectCycle(ListNode head) {
if (head == null || head.next == null) return null;
ListNode slow = head;
ListNode fast = head;
// Phase 1: Cycle আছে কিনা detect করি এবং meet point খুঁজি
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
// Phase 2: Cycle-এর শুরু খুঁজি
slow = head; // Slow-কে head-এ পাঠাই
// দুটো pointer এক step করে এগোয়
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow; // Cycle শুরুর node
}
}
return null; // Cycle নেই
}
public static void main(String[] args) {
LinkedListCycleII solution = new LinkedListCycleII();
// List: 3→2→0→-4→(back to 2)
ListNode head = new ListNode(3);
ListNode node2 = new ListNode(2);
ListNode node3 = new ListNode(0);
ListNode node4 = new ListNode(-4);
head.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node2; // Cycle তৈরি করি
ListNode cycleStart = solution.detectCycle(head);
System.out.println(cycleStart != null ? cycleStart.val : "No cycle");
// Output: 2
// No cycle case
ListNode head2 = new ListNode(1);
head2.next = new ListNode(2);
System.out.println(solution.detectCycle(head2)); // Output: null
}
}
সময় জটিলতা: O(n) | স্থান জটিলতা: O(1)
সমস্যা ৪: Reverse Nodes in k-Group
সমস্যার বিবরণ
একটি linked list এবং একটি integer k দেওয়া আছে। List-এর প্রতিটি k-টি node-এর group reverse করতে হবে। শেষে k-এর কম node থাকলে তাদের as-is রাখতে হবে।
উদাহরণ
Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]
কারণ: [1,2] → [2,1], [3,4] → [4,3], [5] → [5] (k=2 এর কম)
Input: head = [1,2,3,4,5], k = 3
Output: [3,2,1,4,5]
কারণ: [1,2,3] → [3,2,1], [4,5] → [4,5] (k=3 এর কম)
চিন্তার পদ্ধতি
Recursion ব্যবহার করব। প্রথমে k-টি node আছে কিনা check করব। থাকলে সেই k-টি node reverse করব। Reversed group-এর শেষ node-এর next-এ recursively বাকি list-এর result যোগ করব।
সমাধান (Java)
public class ReverseKGroup {
static class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; }
}
public ListNode reverseKGroup(ListNode head, int k) {
// k-টি node আছে কিনা check করি
ListNode check = head;
int count = 0;
while (check != null && count < k) {
check = check.next;
count++;
}
// k-টি node না থাকলে as-is return করি
if (count < k) return head;
// k-টি node reverse করি
ListNode prev = null;
ListNode current = head;
for (int i = 0; i < k; i++) {
ListNode next = current.next;
current.next = prev;
prev = current;
current = next;
}
// head এখন reversed group-এর শেষে আছে
// Recursively বাকি list process করি
head.next = reverseKGroup(current, k);
// prev হলো reversed group-এর নতুন head
return prev;
}
private static String listToString(ListNode head) {
StringBuilder sb = new StringBuilder("[");
while (head != null) {
sb.append(head.val);
if (head.next != null) sb.append(",");
head = head.next;
}
return sb.append("]").toString();
}
public static void main(String[] args) {
ReverseKGroup solution = new ReverseKGroup();
// List: 1→2→3→4→5, k=2
ListNode head1 = new ListNode(1);
head1.next = new ListNode(2);
head1.next.next = new ListNode(3);
head1.next.next.next = new ListNode(4);
head1.next.next.next.next = new ListNode(5);
System.out.println(listToString(solution.reverseKGroup(head1, 2)));
// Output: [2,1,4,3,5]
// List: 1→2→3→4→5, k=3
ListNode head2 = new ListNode(1);
head2.next = new ListNode(2);
head2.next.next = new ListNode(3);
head2.next.next.next = new ListNode(4);
head2.next.next.next.next = new ListNode(5);
System.out.println(listToString(solution.reverseKGroup(head2, 3)));
// Output: [3,2,1,4,5]
}
}
সময় জটিলতা: O(n) | স্থান জটিলতা: O(n/k) recursion stack
সমস্যা ৫: LRU Cache
সমস্যার বিবরণ
LRU (Least Recently Used) Cache implement করতে হবে যেখানে দুটি operation থাকবে। get(key) — key থাকলে value return করবে, না থাকলে -1। put(key, value) — key-value pair যোগ করবে। Cache full হলে সবচেয়ে কম recently used item সরিয়ে দেবে। উভয় operation O(1) time-এ করতে হবে।
উদাহরণ
LRUCache cache = new LRUCache(2); // capacity = 2
cache.put(1, 1); // cache: {1=1}
cache.put(2, 2); // cache: {1=1, 2=2}
cache.get(1); // return 1, cache: {2=2, 1=1} (1 recently used)
cache.put(3, 3); // cache full → 2 evict হয়, cache: {1=1, 3=3}
cache.get(2); // return -1 (not found)
cache.put(4, 4); // cache full → 1 evict হয়, cache: {3=3, 4=4}
cache.get(1); // return -1 (not found)
cache.get(3); // return 3
cache.get(4); // return 4
চিন্তার পদ্ধতি
HashMap + Doubly Linked List ব্যবহার করব। HashMap O(1) lookup দেবে। Doubly Linked List order track করবে — সবচেয়ে recently used head-এর কাছে, সবচেয়ে least recently used tail-এর কাছে। Get ও Put-এ node-কে head-এ সরাব। Cache full হলে tail remove করব।
সমাধান (Java)
import java.util.*;
public class LRUCache {
// Doubly Linked List Node
static class Node {
int key, value;
Node prev, next;
Node(int key, int value) {
this.key = key;
this.value = value;
}
}
private final int capacity;
private final Map<Integer, Node> map = new HashMap<>();
private final Node head = new Node(0, 0); // Dummy head (most recent)
private final Node tail = new Node(0, 0); // Dummy tail (least recent)
public LRUCache(int capacity) {
this.capacity = capacity;
head.next = tail;
tail.prev = head;
}
public int get(int key) {
if (!map.containsKey(key)) return -1;
Node node = map.get(key);
moveToHead(node); // Recently used → head-এর কাছে সরাই
return node.value;
}
public void put(int key, int value) {
if (map.containsKey(key)) {
Node node = map.get(key);
node.value = value;
moveToHead(node);
} else {
Node newNode = new Node(key, value);
map.put(key, newNode);
addToHead(newNode);
if (map.size() > capacity) {
// LRU item (tail-এর আগের node) সরিয়ে দিই
Node lruNode = removeTail();
map.remove(lruNode.key);
}
}
}
private void addToHead(Node node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
private void removeNode(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void moveToHead(Node node) {
removeNode(node);
addToHead(node);
}
private Node removeTail() {
Node lruNode = tail.prev;
removeNode(lruNode);
return lruNode;
}
public static void main(String[] args) {
LRUCache cache = new LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
System.out.println(cache.get(1)); // Output: 1
cache.put(3, 3);
System.out.println(cache.get(2)); // Output: -1 (evicted)
cache.put(4, 4);
System.out.println(cache.get(1)); // Output: -1 (evicted)
System.out.println(cache.get(3)); // Output: 3
System.out.println(cache.get(4)); // Output: 4
}
}
সময় জটিলতা: get O(1), put O(1) | স্থান জটিলতা: O(capacity)
সারসংক্ষেপ
| সমস্যা | পদ্ধতি | Data Structure | সময় জটিলতা | স্থান জটিলতা |
|---|---|---|---|---|
| Add Two Numbers | Carry-based Traversal | Linked List | O(max(m,n)) | O(max(m,n)) |
| Remove Nth From End | Two Pointers (Fast & Slow) | Linked List | O(n) | O(1) |
| Linked List Cycle II | Floyd's Algorithm | Two Pointers | O(n) | O(1) |
| Reverse Nodes in k-Group | Recursion + Reversal | Linked List | O(n) | O(n/k) |
| LRU Cache | HashMap + Doubly Linked List | HashMap + DLL | O(1) | O(capacity) |
Linked List সমস্যার মূল কৌশল: বেশিরভাগ সমস্যায় Two Pointers (Fast & Slow) technique কাজে আসে — cycle detection, middle finding, Nth from end। Dummy head node ব্যবহার করলে edge case (empty list, single node) handle করা সহজ হয়। Reversal সমস্যায় তিনটি pointer (prev, current, next) ব্যবহার করুন। Complex data structure সমস্যায় (যেমন LRU Cache) Linked List + HashMap combination শক্তিশালী সমাধান দেয়।