009 — Remove Nth Node From End of List

Source

• Original source: Classic linked list exercise
• Platform: LeetCode — https://leetcode.com/problems/remove-nth-node-from-end-of-list/
• Topic: linked list
• Difficulty: Medium
• Pattern: runner + dummy head (fixed-gap two pointers)
• Basic idea inherited from: slow/fast (problem 3, 4), কিন্তু গতির অনুপাতের বদলে একটা স্থির gap

1. Problem in simple words

একটা singly linked list দেওয়া আর একটা সংখ্যা n। তোমাকে শেষ থেকে গুনে n নম্বর node-টা মুছে দিতে হবে, আর সেটা মাত্র একবার list-এর উপর হেঁটে। নতুন head return করো।

list: 1 -> 2 -> 3 -> 4 -> 5 ,  n = 2
শেষ থেকে 2য় = node 4 ,  মুছে ফেলো
ফল : 1 -> 2 -> 3 -> 5

2. Which basic idea does this inherit from?

এর শিকড় problem 3 আর 4-এর দুই-pointer খেলায়। তবে সেখানে গতি ছিল ভিন্ন (এক ঘর বনাম দুই ঘর); এখানে দুজনের গতি একই, কিন্তু তাদের মধ্যে একটা স্থির ফাঁক (gap) n ঘরের। এই "fixed gap" idea-টাই নতুন — runner pattern-এর আরেকটা রূপ।

3. What is the hidden math or logic?

লুকানো অঙ্ক সরল: যদি দুটো pointer-এর মধ্যে ঠিক n ঘরের দূরত্ব রাখি আর সামনেরজন list-এর শেষে (None) পৌঁছায়, তখন পিছনেরজন থাকবে ঠিক শেষ থেকে n নম্বর node-এ। মুছতে হলে আবার তার আগের node দরকার, তাই dummy থেকে শুরু করে gap-টা n + 1 রাখি — তাহলে পিছনেরজন থামে মুছে-ফেলা node-এর ঠিক আগে।

4. Which data structure is needed?

কোনো extra structure নয় — শুধু একটা dummy head আর দুটো pointer (fast, slow)। dummy থাকায় আসল head মুছে ফেললেও আলাদা special case সামলাতে হয় না।

5. Why this data structure fits

Linked list-এ আমরা শেষ থেকে index করতে পারি না, length-ও আগে জানা নেই। কিন্তু দুটো pointer-এর মধ্যে একটা স্থির gap রাখলে সামনেরজনই length-এর কাজ মেপে দেয় — পিছনেরজন আপনাআপনি সঠিক জায়গায় থামে। dummy head-টা O(1)-তে head-মোছা case সহজ করে দেয়।

6. Real-life analogy

ভাবো দুজন একই গতিতে হাঁটছে, কিন্তু একজন আরেকজনের চেয়ে ঠিক n কদম এগিয়ে। সামনেরজন যখন রাস্তার শেষ মাথায় পৌঁছায়, পিছনেরজন তখন ঠিক "শেষ থেকে n কদম" দূরত্বে দাঁড়িয়ে — মাপজোক ছাড়াই দূরত্বটা ধরে রাখা গেল।

7. Visual explanation

fast কে আগে n + 1 ঘর এগোও, তারপর দুজনে একসাথে। 1->2->3->4->5, n = 2:

dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> None

fast কে n+1 = 3 ঘর এগোও:
    slow=dummy, fast=3

একসাথে এগোও (fast শেষ না হওয়া পর্যন্ত):
    slow=1, fast=4
    slow=2, fast=5
    slow=3, fast=None  ← থামো

slow = 3 , মুছতে হবে slow.next = 4
slow.next = slow.next.next  →  3 -> 5
ফল: 1 -> 2 -> 3 -> 5

8. Example input and output

Input : 1 -> 2 -> 3 -> 4 -> 5 , n = 2   -> Output: 1 -> 2 -> 3 -> 5

Edge 1 (head মুছে যায়): 1 -> 2 , n = 2   -> Output: 2
Edge 2 (একটা node)    : 1 , n = 1        -> Output: None (খালি)
Edge 3 (শেষটা মুছে)   : 1 -> 2 -> 3 , n = 1 -> Output: 1 -> 2

9. Brute force thinking

সরল চিন্তা: প্রথমে পুরো list একবার ঘুরে length L গোনো। তারপর আবার head থেকে শুরু করে L - n ঘর এগিয়ে গিয়ে সেই node-এর আগেরটায় থামো, আর তার next bypass করো।

pass 1: 1->2->3->4->5 গুনে L = 5
pass 2: L - n = 3 ঘর এগিয়ে node 3-এ থামো, 3.next bypass

10. Why brute force is slow

এটা ঠিক উত্তর দেয়, কিন্তু list-এর উপর দুবার হাঁটে (একবার গুনতে, একবার পৌঁছাতে)। problem নিজেই বলছে এক পাসে করতে — runner + fixed gap দিয়ে এক পাসেই হয়ে যায়, কারণ gap-টাই length-এর হিসাব রেখে দেয়।

11. Key observation

মূল observation: শেষ থেকে দূরত্ব মাপতে length গোনার দরকার নেই। দুটো pointer-এর মধ্যে n ঘরের ফাঁক রেখে দিলে, সামনেরজন শেষ ছোঁয়ার মুহূর্তে পিছনেরজন আপনাআপনি শেষ থেকে n নম্বরে থাকে।

12. Optimized intuition

dummy থেকে দুজনকে শুরু করো। fast কে আগে n + 1 ঘর এগিয়ে দাও (যাতে gap শেষে মুছে-ফেলা node-এর আগের জায়গায় বসে)। তারপর fast None না হওয়া পর্যন্ত দুজনে একসাথে এগোও। থামলে slow থাকবে target-এর ঠিক আগে — slow.next = slow.next.next করে bypass করে দাও।

13. Thinking tweak

মোচড়: "length গুনে L − n-এ যাব" না ভেবে ভাবো — "দুজনের মধ্যে n+1 ঘরের ফাঁক বানাই, সামনেরজনকে প্রান্তে ছেড়ে দিই; ও শেষে গেলে পিছনেরজন এমনিতেই কাটার ঠিক আগে।" গোনা বাদ, ফাঁক দিয়ে কাজ।

14. Step-by-step dry run

Input 1 -> 2 -> 3 -> 4 -> 5, n = 2:

1. dummy -> 1 -> ... -> 5; slow = fast = dummy
2. fast কে n + 1 = 3 ঘর এগোও → fast = 3, slow = dummy
3. একসাথে: fast = 4, slow = 1
4. একসাথে: fast = 5, slow = 2
5. একসাথে: fast = None, slow = 3 → থামো
6. slow.next (= 4) bypass: slow.next = slow.next.next → 3 -> 5
7. return dummy.next = 1 -> 2 -> 3 -> 5

15. Python solution

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

def remove_nth_from_end(head, n):
    dummy = ListNode(0, head)     # dummy: head মুছলেও special case এড়ায়
    slow = fast = dummy
    for _ in range(n + 1):        # fast কে n+1 ঘর এগোও (gap বানাও)
        fast = fast.next
    while fast:                   # দুজনে একসাথে; fast শেষে গেলে slow কাটার আগে
        fast = fast.next
        slow = slow.next
    slow.next = slow.next.next    # target node bypass করো
    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(remove_nth_from_end(build([1, 2, 3, 4, 5]), 2)) == [1, 2, 3, 5]
assert to_list(remove_nth_from_end(build([1, 2]), 2)) == [2]          # head মুছে যায়
assert to_list(remove_nth_from_end(build([1]), 1)) == []              # একমাত্র node
assert to_list(remove_nth_from_end(build([1, 2, 3]), 1)) == [1, 2]    # শেষটা মুছে
print("সব test pass!")

16. Line-by-line code explanation

• dummy = ListNode(0, head) — নকল head; আসল head মুছলেও যাতে আলাদা করে ভাবতে না হয়।
• slow = fast = dummy — দুজনেই dummy থেকে শুরু, gap শূন্য।
• for _ in range(n + 1): — fast কে n + 1 ঘর এগোই, যাতে শেষে gap কাটার আগের জায়গায় বসে।
• while fast: — fast None না হওয়া পর্যন্ত দুজনে এক ঘর করে একসাথে এগোয়।
• slow.next = slow.next.next — slow এখন target-এর আগে; তার পরেরটা (target) bypass।
• return dummy.next — আসল (সম্ভবত বদলানো) head।

17. Output walkthrough

build([1,2,3,4,5]) বানায় 1->2->3->4->5; n=2-তে node 4 মুছে [1,2,3,5]। [1,2], n=2-তে head মুছে [2]। [1], n=1-তে list খালি → []। [1,2,3], n=1-তে শেষটা মুছে [1,2]। সব assert pass → সব test pass!।

18. Time complexity

O(L) — L list-এর দৈর্ঘ্য; fast একবারই শেষ পর্যন্ত যায়, slow তার পিছনে — মোট এক পাস।

19. Space complexity

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

20. Common mistakes

• fast কে n-এর বদলে n + 1 ঘর না এগোনো — তখন slow থামে target-এ, তার আগে নয়, ফলে bypass ভুল হয়।
• dummy head না নেওয়া — তখন আসল head মুছে ফেলার case আলাদা করে সামলাতে হয়, code bug-প্রবণ।
• n list-length-এর সমান হলে (head মুছে যাবে) আলাদা করে না ভাবা — dummy থাকলে এটা এমনিতেই ঠিক থাকে।

21. Which basic problem this inherits from

ভিত্তি: problem 3 (003-linked-list-cycle.md) আর problem 4 (004-middle-of-list.md)-এর দুই-pointer skeleton; এখানে গতির বদলে স্থির gap। dummy head কৌশল problem 2 (002-merge-two-sorted-lists.md) থেকে।

22. Similar harder problems

• Middle of the Linked List (এক পাসে দূরত্ব) — https://leetcode.com/problems/middle-of-the-linked-list/ (এই tracker-এর #4)
• Rotate List (runner gap + modular k) — https://leetcode.com/problems/rotate-list/ (#16)
• Swap Nodes in Pairs (dummy + rewiring) — https://leetcode.com/problems/swap-nodes-in-pairs/ (#12)

23. Pattern learned

Runner with fixed gap: দুটো pointer-এর মধ্যে স্থির দূরত্ব রেখে সামনেরজনকে প্রান্তে ছেড়ে দাও — পিছনেরজন আপনাআপনি "শেষ থেকে n" জায়গায় থামে; length গোনা ছাড়াই এক পাসে।

24. Final summary

ভবিষ্যতের আমাকে: "শেষ থেকে nth লাগবে? length গুনো না — dummy থেকে fast কে n+1 ঘর এগিয়ে দাও, তারপর দুজনে একসাথে; fast None হলে slow কাটার ঠিক আগে।" head-মোছা case-এর জন্য dummy অবশ্যই রাখবে।

25. JavaScript solution (with test cases)

const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };

class ListNode {
  constructor(val = 0, next = null) { this.val = val; this.next = next; }
}
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 removeNthFromEnd(head, n) {
  const dummy = new ListNode(0, head);   // dummy: head মুছলেও special case এড়ায়
  let slow = dummy, fast = dummy;
  for (let i = 0; i < n + 1; i++) fast = fast.next;  // fast কে n+1 ঘর এগোও
  while (fast) { fast = fast.next; slow = slow.next; }  // একসাথে এগোও
  slow.next = slow.next.next;            // target node bypass করো
  return dummy.next;
}

// ---- test cases ----
const eq = (a, b) => JSON.stringify(a) === JSON.stringify(b);
assert(eq(listToArray(removeNthFromEnd(arrayToList([1, 2, 3, 4, 5]), 2)), [1, 2, 3, 5]), "main");
assert(eq(listToArray(removeNthFromEnd(arrayToList([1, 2]), 2)), [2]), "head মুছে যায়");
assert(eq(listToArray(removeNthFromEnd(arrayToList([1]), 1)), []), "একমাত্র node");
assert(eq(listToArray(removeNthFromEnd(arrayToList([1, 2, 3]), 1)), [1, 2]), "শেষটা মুছে");
console.log("সব JS test pass!");

JS টীকা: new ListNode(0, head) দিয়ে dummy বানাই যাতে আসল head মুছে গেলেও আলাদা special case না লাগে — শেষে dummy.next ফেরাই। মূল চাবি: fast-কে n নয়, n + 1 ঘর এগোতে হবে, যাতে loop শেষে slow মুছে-ফেলা node-এর ঠিক আগে থামে আর slow.next = slow.next.next দিয়ে bypass করা যায়। এক পাসেই হয়, length গোনা লাগে না।

26. TypeScript solution (with test cases)

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 removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  const dummy: ListNode = node(0, head);
  let slow: ListNode = dummy;
  let fast: ListNode = dummy;
  for (let i = 0; i < n + 1; i++) fast = fast.next!;  // n+1 ঘর (ধরে নিচ্ছি n বৈধ)
  while (fast) { fast = fast.next!; slow = slow.next!; }
  slow.next = slow.next!.next;
  return dummy.next;
}

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

TS টীকা: slow/fast কে ListNode (non-null) ধরেছি কারণ দুটোই dummy থেকে শুরু, আর problem নিশ্চিত করে n বৈধ — তাই advance করার সময় fast.next!-এ non-null assertion দিই। কিন্তু loop-শর্ত while (fast) truthiness-এ চলে বলে fast কে আবার ListNode | null-এর মতো আচরণ করতে হয়; এই দ্বৈততা সামলাতে assertion সবচেয়ে সরল উপায়। dummy-head trick head-মোছা edge কে টাইপ-নিরাপদভাবে ঢাকে।

27. কোথায় কাজে লাগে (real-world use)

• "Remove from end" operations: log buffer বা recent-list থেকে "শেষ থেকে k-তম" entry মুছতে — length না জেনেই।
• Streaming/single-pass deletion: যেখানে list দুবার traverse করা ব্যয়বহুল (বড় বা remote data)।
• Sliding-window endpoints: fixed-gap দুই pointer দিয়ে window-এর দুই প্রান্ত একসাথে রাখা।
• Undo last-N: action-history-তে "শেষ থেকে n-তম action" টার্গেট করতে।
• Bounded cache trimming: fixed-gap runner দিয়ে tail থেকে নির্দিষ্ট দূরত্বের node চিহ্নিত করা।

এক কথায়, "শেষ থেকে দূরত্ব" এক পাসে চাই বা head-মোছার edge পরিষ্কার রাখতে চাই — fixed-gap runner + dummy head-ই আদর্শ pattern।

---

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