কনটেন্টে যান

017 — Sort List

Problem link ও উৎস

  • Original source: Classic linked list exercise
  • Platform: LeetCode — https://leetcode.com/problems/sort-list/
  • Topic: linked list
  • Difficulty: Medium
  • Pattern: merge sort on chains
  • Basic idea inherited from: middle দিয়ে split (problem 4) + merge two (problem 2), recursively

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

একটা linked list দেওয়া, যার value গুলো এলোমেলো। তোমাকে এটাকে ছোট-থেকে-বড় (ascending) ক্রমে sort করতে হবে আর sorted list-এর head return করতে হবে। লক্ষ্য: O(n log n) সময়ে — মানে সহজ O(n²) sort চলবে না।

উদাহরণ
আগে : 4 -> 2 -> 1 -> 3
পরে : 1 -> 2 -> 3 -> 4

Input ও output

উদাহরণ
Input : 4 -> 2 -> 1 -> 3          -> Output: 1 -> 2 -> 3 -> 4
Input : -1 -> 5 -> 3 -> 4 -> 0    -> Output: -1 -> 0 -> 3 -> 4 -> 5

Edge 1 (খালি list):  None         -> Output: None
Edge 2 (একটা node):  1            -> Output: 1
Edge 3 (duplicate):  3 -> 3 -> 1  -> Output: 1 -> 3 -> 3

চেনা উদাহরণে বোঝা

একগাদা পরীক্ষার খাতা sort করছ। একা পুরোটা সামলানো কঠিন, তাই তাড়াটা অর্ধেক অর্ধেক করে ভাগ করে দুজনকে দিলে; তারা আবার ভাগ করল — যতক্ষণ না হাতে এক-একটা খাতা থাকে (এমনিতেই sorted)। তারপর দুজন দুজন মিলে দুটো sorted তাড়া এক করে উপরে উঠতে থাকল — শেষে পুরোটা sorted।

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

এটা দুটো পুরোনো skeleton recursively জোড়া — খাঁটি merge sort, কিন্তু array নয়, linked list-এ:

দুটোকে recursion-এ মুড়ে দিলেই পুরো sort।

ভেতরের যুক্তি

লুকানো logic হলো divide and conquer-এর সেই recurrence: T(n) = 2·T(n/2) + O(n)। প্রতি level-এ পুরো n node merge হয় (O(n)), আর প্রতিবার অর্ধেক করে ভাঙায় level-এর সংখ্যা log n। তাই মোট O(n log n)। merge sort তাই array-র মতো linked list-এও সমান দক্ষ — বরং linked list-এ merge step-এ extra space লাগে না।

কী দিয়ে তথ্য রাখব

কোনো নতুন container নয় — list নিজেই যথেষ্ট। লাগে slow/fast pointer (split-এর জন্য), dummy head (merge-এর জন্য), আর recursion-এর জন্য call stack। তাই extra space মূলত recursion depth = O(log n)।

এটি কেন উপযুক্ত

Merge sort-এর জন্য linked list আদর্শ: array merge-এ দুই অর্ধ জোড়াতে O(n) extra array লাগে, কিন্তু linked list-এ merge শুধু arrow ঘোরানো — O(1) extra (recursion stack বাদে)। আর random access না থাকায় quicksort-এর pivot ভাগ ঝামেলার; তাই linked list-এ merge sort-ই স্বাভাবিক পছন্দ।

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

সরল চিন্তা: সব value একটা array-তে তুলে নাও, array-টা sort করো (sorted()), তারপর sorted value দিয়ে নতুন list বানাও বা পুরোনো node-এ value বসাও।

উদাহরণ
4->2->1->3 -> [4,2,1,3] -> sort -> [1,2,3,4] -> 1->2->3->4

কোথায় বেশি কাজ হচ্ছে

আসলে এটা O(n log n) time দেয় (Python-এর sort), কিন্তু O(n) extra space নেয় (array)। আর এটা linked list-এর কাঠামোকে কাজে লাগায় না — node-এর arrow ঘুরিয়ে in-place merge করলে extra array লাগত না। Interview-তে চাওয়া হয় list-এর উপরেই merge sort, যাতে extra space কমে (শুধু recursion stack)।

যে বিষয়টি খেয়াল করতে হবে

মূল observation: একটা একক node সবসময় sorted। তাই list-কে বারবার অর্ধেক করে ভাঙতে থাকো যতক্ষণ না প্রতিটা টুকরো এক-node হয় (তখন এমনিতেই sorted), তারপর জোড়ায় জোড়ায় merge করে উপরে ওঠো — এটাই merge sort-এর প্রাণ।

আরও কম কাজে সমাধান

Recursion-এ ভাবো: base case — list খালি বা এক-node হলে already sorted, ফেরাও। নাহলে slow/fast দিয়ে middle খুঁজে দুই ভাগে কাটো, দুই ভাগকে recursively sort করো, তারপর problem 2-এর merge দিয়ে দুই sorted অর্ধ জোড়ো। উপরে উঠতে উঠতে পুরো list sorted।

ভাবনার পরিবর্তন

মোচড়: "পুরো list কীভাবে sort করব" না ভেবে ভাবো — "অর্ধেক করে কেটে দুজনকে দিয়ে দিই; ওরা sorted করে আনলে আমি শুধু দুটো sorted জিনিস merge করব।" বড় কাজটা নিজেকে সমর্পণ করে দাও recursion-এর হাতে; তোমার দায়িত্ব শুধু split আর merge।

ছবিতে বোঝা

4 -> 2 -> 1 -> 3 দিয়ে split-merge গাছ:

উদাহরণ
              [4, 2, 1, 3]
            split (middle)
          /                \
     [4, 2]                [1, 3]
    /      \              /      \
  [4]      [2]          [1]      [3]
    \      /              \      /
   merge → [2, 4]        merge → [1, 3]
            \              /
             merge → [1, 2, 3, 4]

ছোট input-এ ধাপে ধাপে

Input 4 -> 2 -> 1 -> 3:

  1. split (slow=head, fast=head.next): slow node 2-এ থামে → left = 4 -> 2, right = 1 -> 3।
  2. sort(4 -> 2): আবার split → [4], [2]; merge → 2 -> 4।
  3. sort(1 -> 3): split → [1], [3]; merge → 1 -> 3।
  4. উপরে merge: merge(2 -> 4, 1 -> 3) → দুই মাথা তুলনা করে 1 -> 2 -> 3 -> 4।
  5. ফল: 1 -> 2 -> 3 -> 4।

কোড ও ব্যাখ্যা

Python

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

def merge_two(l1, l2):
    dummy = ListNode()      # dummy head — head-এর special case এড়াতে
    tail = dummy
    while l1 and l2:
        if l1.val <= l2.val:
            tail.next = l1
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next
    tail.next = l1 if l1 else l2   # যেটা বাকি, পুরো জুড়ে দাও
    return dummy.next

def sort_list(head):
    if not head or not head.next:
        return head         # খালি বা এক-node → already sorted

    # split: middle খোঁজো (fast = head.next দিয়ে দুই-node case-ও এগোয়)
    slow = head
    fast = head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    mid = slow.next         # দ্বিতীয় অর্ধের শুরু
    slow.next = None        # দুই অর্ধ আলাদা করো

    left = sort_list(head)  # দুই অর্ধ recursively sort
    right = sort_list(mid)
    return merge_two(left, right)

# ---- 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(sort_list(build([4, 2, 1, 3]))) == [1, 2, 3, 4]
assert to_list(sort_list(build([-1, 5, 3, 4, 0]))) == [-1, 0, 3, 4, 5]
assert to_list(sort_list(build([]))) == []
assert to_list(sort_list(build([1]))) == [1]
assert to_list(sort_list(build([2, 1]))) == [1, 2]
assert to_list(sort_list(build([3, 3, 1, 1, 2]))) == [1, 1, 2, 3, 3]
print("সব test pass!")

কোডের প্রতিটি অংশ

  • if not head or not head.next: — base case: খালি বা এক-node already sorted।
  • slow = head; fast = head.next — split-এ এখানে fast এক ঘর এগিয়ে শুরু; এতে দুই-node list-এ slow প্রথম node-এ থামে, যাতে দুই অর্ধই non-empty হয় (নাহলে infinite recursion)।
  • while fast and fast.next: — slow ঠিক first-half-এর শেষে থামবে।
  • mid = slow.next; slow.next = None — list দুই ভাগ।
  • left = sort_list(head); right = sort_list(mid) — recursively দুই অর্ধ sort।
  • merge_two(left, right) — problem 2-এর merge: দুই sorted অর্ধ এক করো।

Output মিলিয়ে দেখা

build([4,2,1,3]) → 4->2->1->3। split → 4->2 ও 1->3; recursively sort → 2->4 ও 1->3; merge → 1->2->3->4 → [1,2,3,4] — assert pass। নেগেটিভ, খালি, এক-node, দুই-node, duplicate — সব pass হয়ে শেষে print: সব test pass!।

খরচ ও সাধারণ ভুল

সময়

O(n log n) — প্রতি level-এ সব মিলিয়ে O(n) merge কাজ, আর অর্ধেক করে ভাঙায় log n level; গুণ করলে n log n।

অতিরিক্ত জায়গা

O(log n) — merge নিজে O(1) (arrow ঘোরায়), কিন্তু recursion stack-এর গভীরতা log n। (পুরো iterative bottom-up লিখলে O(1)-এ নামানো যায়।)

যে ভুলগুলো এড়াতে হবে

  • split-এ fast = head রাখা (head.next-এর বদলে) — দুই-node list-এ এক অর্ধ খালি থেকে যায় → infinite recursion / stack overflow।
  • slow.next = None দিয়ে দুই অর্ধ আলাদা করতে ভুলে যাওয়া — তখন merge-এ overlap, ভুল ফল বা loop।
  • base case (খালি/এক-node) না দেওয়া — recursion কখনো থামে না।
  • merge-এ < ব্যবহার করা <=-এর বদলে — duplicate-এ stable order হারাতে পারে।

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

ভিত্তি দুটো: middle দিয়ে split ([004-middle-of-list.md](004-middle-of-list.md)) আর merge two sorted lists ([002-merge-two-sorted-lists.md](002-merge-two-sorted-lists.md))। আটকে গেলে আগে এই দুটো আলাদা করে ঝালিয়ে নাও — sort তাদেরই recursion-এ মোড়ানো রূপ।

পরের অনুশীলন

কৌশলটি মনে রাখুন

Merge sort on a linked list: middle দিয়ে split + sorted merge, recursively — O(n log n) sort যেখানে merge step O(1) extra space-এ হয়।

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে: "list O(n log n)-এ sort? merge sort — middle দিয়ে কাটো, দুই অর্ধ recursively sort করো, তারপর merge।" এক-node সবসময় sorted — সেটাই recursion-এর তলদেশ।

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