# Linked List — delivery manifest ও crate loading

দুই warehouse থেকে batch ID অনুযায়ী সাজানো parcel list এসেছে। বাতিল batch-এর parcel বাদ দিতে হবে। তারপর পূর্ণ crate-এ একসঙ্গে `k`টি parcel উল্টো ক্রমে load হবে; শেষের অসম্পূর্ণ crate আগের ক্রমেই থাকবে। Array বানিয়ে sort/reverse না করে **একই node-এর link বদলে** final manifest তৈরি করো।

**কোর্স-সংযোগ:** Microsoft Module 1-এর linked list, traversal ও operation cost-এর সম্পর্কিত অনুশীলন। এটি সাইটের নিজস্ব guided problem।

## ১. আগে যা পড়বে

| ক্রম | নোট | বোঝার লক্ষ্য |
| --- | --- | --- |
| 1 | [Linked list ধারণা](../03-linked-list/concept.md), [pointer-এর চিত্র](../03-linked-list/visual-explanation.md) | node-এর identity ও value কেন এক নয় |
| 2 | [Cycle detection](../03-linked-list/problems/003-linked-list-cycle.md) | fast/slow pointer কখন মিলবে |
| 3 | [Merge Two Sorted Lists](../03-linked-list/problems/002-merge-two-sorted-lists.md) | dummy head দিয়ে প্রথম node-এর বিশেষ case সরানো |
| 4 | [Remove Elements](../03-linked-list/problems/006-remove-elements.md) | বাদ দেওয়ার সময় previous কেন একই থাকে |
| 5 | [Reverse Linked List](../03-linked-list/problems/001-reverse-linked-list.md), [Reverse k-Group](../03-linked-list/problems/020-reverse-k-group.md) | next হারানোর আগেই বাঁচিয়ে রাখা |

## ২. সমস্যার চুক্তি

`build_manifest(left, right, cancelled, group_size)` একটি `Node` head ফেরাবে। প্রতিটি node-এ integer `value` ও `next` থাকবে। value হলো batch ID; একই batch-এর একাধিক parcel থাকতে পারে। `cancelled`-এ ID থাকলে সেই ID-এর **সব** parcel বাদ যাবে।

- দুই list nondecreasing order-এ থাকবে, cycle থাকবে না, এবং তারা কোনো node share করবে না। মোট `0 ≤ n ≤ 100000`।
- `group_size = k ≥ 1` integer। অবশিষ্ট node-এর মধ্যে প্রতি পূর্ণ `k`-group reverse হবে; ছোট শেষ group অপরিবর্তিত।
- সমান ID-এর merge-এ left list-এর node আগে আসে। কোনো নতুন parcel node তৈরি করবে না; temporary dummy node ব্যবহার করা যাবে।
- **Input consume হবে:** original head ধরে আগের list আবার ব্যবহার করবে না। Node-এর link বদলানোই কাজটির অংশ।
- cycle, shared tail, unsorted input বা invalid k পেলে link বদলানোর আগেই `ValueError`। খালি list বৈধ।

### উদাহরণ

```python
left = from_values([1, 4, 7])
right = from_values([2, 3, 6, 8])
result = build_manifest(left, right, cancelled={3, 7}, group_size=2)
assert to_values(result) == [2, 1, 6, 4, 8]
```

```dsa
kind: linked-list
title: "Merge → বাতিল বাদ → পূর্ণ crate reverse"
steps:
  - label: "দুই sorted manifest merge"
    values: [1, 2, 3, 4, 6, 7, 8]
    active: [2, 5]
    note: "Batch 3 ও 7 বাতিল।"
  - label: "বাতিলের node bypass"
    values: [1, 2, 4, 6, 8]
    note: "দুটি পূর্ণ crate: [1,2] ও [4,6]; শেষ [8] অসম্পূর্ণ।"
  - label: "প্রতি পূর্ণ crate উল্টো"
    values: [2, 1, 6, 4, 8]
    active: [0, 1, 2, 3]
    note: "শেষ 8-এর অবস্থান অপরিবর্তিত; value কপি নয়, link বদলেছে।"
```

## ৩. চারটি guided milestone

### ধাপ A — নিরাপদে list পড়া

প্রথমে `assert_acyclic(head)` লিখো। slow এক ধাপ, fast দুই ধাপ। identity দিয়ে মিলবে: `slow is fast`; একই value থাকলেই cycle নয়। এরপর sorted order যাচাই করে প্রতিটি list-এর শেষ node মনে রাখো।

**কেন শেষ node যথেষ্ট:** দুটি acyclic singly linked list কোনো node share করলে সেই node-এর পরের পুরো পথই shared; তাই তাদের tail একই হবে। দুই nonempty list-এর tail একই হলে reject করো।

**Checkpoint:** self-loop reject হবে; `1 → shared5` এবং `2 → shared5`-ও reject হবে। একই value-সহ আলাদা node বৈধ। এই ধাপের আগে কোনো `next` বদলাবে না।

### ধাপ B — existing node merge

`merge_sorted(left, right)`-এ dummy ও tail রাখো। ছোট head-কে `tail.next` করো, সেই input head এগিয়ে নাও, তারপর tail এগোবে।

**Invariant:** dummy-র পরের অংশ sorted এবং tail তার শেষ node। Hint: তুলনায় `<=` দিলে equal-ID parcel-এর স্থির ক্রম থাকে। শেষের অবশিষ্ট chain একবার link করলেই হবে।

**Checkpoint:** দুই input-এর সব node identity output-এ আছে; sample-এর merge হলো `[1,2,3,4,6,7,8]`।

### ধাপ C — cancelled parcel bypass

`remove_cancelled(head, cancelled)`-এ dummy-কে previous করো। `previous.next.value` বাতিল হলে `previous.next = previous.next.next`। অন্যথায় previous এগোবে।

**Invariant:** previous পর্যন্ত রাখা প্রতিটি node বৈধ। Hint: node বাদ দিলে previous এগিয়ো না; পরেরটিও বাতিল হতে পারে। `cancelled` আগে set করলে membership সাধারণত `O(1)`।

**Checkpoint:** প্রথম node বাতিল, পরপর দুই node বাতিল, এবং সব node বাতিল—তিনটিই পরীক্ষা করো। সব বাদ গেলে head হবে `None`।

### ধাপ D — পূর্ণ group-ই reverse

`reverse_complete_groups(head, k)`-এ `before` হলো group-এর আগের node। আগে `k` ধাপ হেঁটে দেখো group পূর্ণ কি না। পূর্ণ না হলে কাজ শেষ; কোনো pointer বদলাবে না।

পূর্ণ হলে তিনটি anchor রাখো: `first`, `last`, `after = last.next`। reverse করার শুরুতে `previous = after` রাখো; এতে পুরনো first শেষে গিয়েই পরের group-এর সঙ্গে যুক্ত হয়। reverse শেষে `before.next = last`, তারপর নতুন before হবে পুরনো first।

**Invariant:** before-এর আগের group-গুলো final; after-এর পরের chain এখনো untouched। next বদলানোর আগে `following = current.next` রাখতে হবে।

**Checkpoint:** `[1,2,3,4,5], k=2 → [2,1,4,3,5]`; `k=1`-এ আগের ক্রম। `k` বড় হলে পুরো ছোট list অপরিবর্তিত।

## ৪. Unit test ও solution পড়ার নিয়ম

[Python reference implementation](../practice/linked_list_lab.py) · [Unit tests](../practice/test_linked_list_lab.py)

```bash
python -m unittest discover -s practice -p 'test_linked_list_lab.py' -v
```

১০টি test-এ sample, duplicates, empty/all-cancelled, অসম্পূর্ণ group, invalid input এবং **node identity বজায় থাকা** যাচাই হয়। আরও ১৫০ random case-এ একটি সহজ array model-এর সঙ্গে final order মেলানো হয়। শুধু value মিললে pointer solution সঠিক প্রমাণিত হয় না; cycle বা নতুন parcel node তৈরি হওয়াও ধরা চাই।

Reference পড়ার সময় প্রথমে `build_manifest`-এর pipeline দেখো। তারপর group reversal-এর `following`, `previous`, `current` তিন pointer কাগজে trace করো। এই তিনটির অর্থ মুখে বলতে না পারলে code মুখস্থ করে এগিয়ো না।

## ৫. Coverage ও খরচ

| Pattern | কোথায় কাজে লাগল |
| --- | --- |
| Fast/slow pointer | invalid cycle ধরা |
| Shared-tail reasoning | input lists disjoint কি না |
| Dummy node + sorted merge | এক manifest তৈরি |
| Previous/current deletion | cancelled parcel বাদ |
| In-place reversal | পূর্ণ crate-এর order বদল |
| আলাদা অনুশীলন | random pointer copy, palindrome check, digit addition, LRU cache এখানে নেই |

মোট সময় expected `O(n + c)`, যেখানে `c` cancelled ID-এর সংখ্যা। cancellation set `O(c)` memory নেয়; pointer transformation নিজে `O(1)` অতিরিক্ত memory। `to_values` শুধু output দেখা/test-এর জন্য `O(n)` array বানায়; মূল algorithm সেটি ব্যবহার করে না।