Skip to content

016 — Rotate List

Source

  • Original source: Classic linked list exercise
  • Platform: LeetCode — https://leetcode.com/problems/rotate-list/
  • Topic: linked list
  • Difficulty: Medium
  • Pattern: runner / close-the-ring
  • Basic idea inherited from: runner gap (problem 9) + modular k (math fundamentals)

1. Problem in simple words

একটা linked list আর একটা সংখ্যা k দেওয়া। তোমাকে list-টাকে ডানদিকে k ঘর rotate করতে হবে — মানে শেষের দিকের k-টা node তুলে এনে সামনে বসাতে হবে, ক্রম ঠিক রেখে। নতুন head return করো।

list : 1 -> 2 -> 3 -> 4 -> 5 ,  k = 2
ফল   : 4 -> 5 -> 1 -> 2 -> 3

k list-এর দৈর্ঘ্যের চেয়ে বড় হতে পারে — তখন wrap করতে হবে (পুরো এক পাক ঘুরলে list অপরিবর্তিত)।

2. Which basic idea does this inherit from?

দুটো পুরোনো idea মিলেছে:

  • Runner gap (problem 9 — nth-from-end): শেষ থেকে গুনে একটা নির্দিষ্ট জায়গায় pointer বসানোর ভাবনা। এখানেও আমরা "শেষ থেকে k ঘর আগের" node-টা খুঁজি, যেটা হবে নতুন tail।
  • Modular arithmetic (math fundamentals): k % length — কারণ length-এর গুণিতক বার ঘোরালে list একই থাকে।

3. What is the hidden math or logic?

দুটো লুকানো গণিত:

  • Modulo: length L হলে k আর k % L একই ফল দেয় (পুরো পাক ঘোরা = কিছুই না)। তাই প্রথমেই k %= L করে নিই — না করলে বড় k-তে অসংখ্য বাড়তি ঘোরা।
  • নতুন break-point: ডানে k ঘর rotate মানে নতুন head হলো শেষ থেকে k-তম node, অর্থাৎ সামনে থেকে L - k-তম node। তাই নতুন tail বসে index L - k - 1-এ।

4. Which data structure is needed?

কোনো নতুন structure নয় — শুধু কয়েকটা pointer (tail, new_tail) আর length গোনার একটা counter। O(1) extra space।

5. Why this data structure fits

Linked list-এ শেষ node-কে head-এর সাথে জুড়ে দেওয়া (ring বানানো) মাত্র একটা arrow সেট — O(1)। rotate মানে আসলে "ring-টা একটা নতুন জায়গায় কেটে দেওয়া"। তাই আলাদা কোনো structure লাগে না; pointer দিয়ে ring বানিয়ে, ঠিক জায়গায় কেটে দিলেই rotate হয়ে যায়।

6. Real-life analogy

একটা গোল চাবির রিং ভাবো, তাতে কয়েকটা চাবি ক্রমে গাঁথা। rotate করা মানে রিংটা আসলে একই — তুমি শুধু ঠিক করছ "শুরু" ধরবে কোন চাবি থেকে। তাই list-এর লেজ আর মাথা জুড়ে একটা রিং বানাও, তারপর নতুন জায়গায় রিংটা কেটে দাও — নতুন শুরু পেয়ে গেলে।

7. Visual explanation

1 -> 2 -> 3 -> 4 -> 5, k = 2 (L = 5):

ধাপ ১ — length + tail:  L = 5, tail = 5
ধাপ ২ — k %= L:         k = 2 % 5 = 2
ধাপ ৩ — ring বানাও:     5.next = 1   (লেজ মাথায় জোড়া)
ধাপ ৪ — new_tail index = L-k-1 = 2 → node 3
        new_head = new_tail.next = 4
        new_tail.next = None   (রিং কাটো)

ফল: 4 -> 5 -> 1 -> 2 -> 3

8. Example input and output

Input : 1 -> 2 -> 3 -> 4 -> 5 , k = 2   -> Output: 4 -> 5 -> 1 -> 2 -> 3
Input : 0 -> 1 -> 2 , k = 4              -> Output: 2 -> 0 -> 1   (4 % 3 = 1)

Edge 1 (k = 0):        1 -> 2 -> 3 , k=0  -> Output: 1 -> 2 -> 3
Edge 2 (k = L-এর গুণিতক): 1 -> 2 -> 3 , k=3 -> Output: 1 -> 2 -> 3
Edge 3 (খালি list):     None , k=1        -> Output: None
Edge 4 (একটা node):     7 , k=99          -> Output: 7

9. Brute force thinking

সরল চিন্তা: rotate-right-by-1 একটা helper বানাও (শেষ node তুলে এনে সামনে বসাও), তারপর সেটা k বার চালাও।

1->2->3->4->5  (rotate 1) -> 5->1->2->3->4
               (rotate 1) -> 4->5->1->2->3   (k=2 শেষ)

10. Why brute force is slow

প্রতিবার rotate-by-1-এ শেষ node খুঁজতে পুরো list হাঁটতে হয় — O(n)। সেটা k বার করলে O(n·k)। k বড় হলে (বা k >> n) এটা ভয়ানক ধীর। অথচ k % n করলে আর ring trick ব্যবহার করলে পুরোটা এক-দুই পাসেই শেষ।

11. Key observation

মূল observation: rotate করা মানে list-টাকে একটা ring ধরে শুধু "শুরুর বিন্দু" সরানো। তাই বারবার ঘোরানোর দরকার নেই — একবার ring বানিয়ে, সঠিক জায়গায় (index L-k-1-এর পরে) কেটে দিলেই হয়।

12. Optimized intuition

প্রথমে length L আর tail বের করো (এক পাস)। k %= L করো; k == 0 হলে কিছুই বদলায় না, head ফেরাও। নাহলে tail.next = head দিয়ে ring বানাও, head থেকে L - k - 1 ঘর এগিয়ে new_tail-এ থামো, new_head = new_tail.next নাও, আর new_tail.next = None দিয়ে ring কেটে দাও।

13. Thinking tweak

মোচড়: "k বার ঘোরাব" না ভেবে ভাবো — "list তো আসলে একটা বৃত্ত; আমি শুধু কোথায় কাটব সেটা ঠিক করছি।" আর k বড় হলে আগে k %= L করে নাও, যাতে অপ্রয়োজনীয় পাক বাদ যায়। ঘোরানো বাদ, একটাই কাটা।

14. Step-by-step dry run

Input 0 -> 1 -> 2, k = 4:

  1. Length + tail: হাঁটতে হাঁটতে L = 3, tail = 2।
  2. k %= L → k = 4 % 3 = 1।
  3. k != 0, তাই ring: tail.next = head → 2.next = 0।
  4. steps = L - k - 1 = 3 - 1 - 1 = 1; new_tail = 0, এক ঘর এগিয়ে new_tail = 1।
  5. new_head = new_tail.next = 2; new_tail.next = None → ring কাটলো।
  6. ফল: 2 -> 0 -> 1।

15. Python solution

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

def rotate_right(head, k):
    if not head or not head.next:
        return head            # খালি বা একক node — rotate-এ কিছু বদলায় না

    # ১) length আর শেষ node (tail) বের করো
    length = 1
    tail = head
    while tail.next:
        tail = tail.next
        length += 1

    # ২) k বড় হলে wrap; পুরো পাক ঘোরা = কিছুই না
    k %= length
    if k == 0:
        return head

    # ৩) ring বানিয়ে নতুন জায়গায় কাটো
    tail.next = head                 # লেজ মাথায় জুড়ে বৃত্ত
    steps = length - k - 1           # new tail এতগুলো ঘর head থেকে
    new_tail = head
    for _ in range(steps):
        new_tail = new_tail.next
    new_head = new_tail.next
    new_tail.next = None             # বৃত্ত কাটো
    return new_head

# ---- 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(rotate_right(build([1, 2, 3, 4, 5]), 2)) == [4, 5, 1, 2, 3]
assert to_list(rotate_right(build([0, 1, 2]), 4)) == [2, 0, 1]   # 4 % 3 = 1
assert to_list(rotate_right(build([1, 2, 3]), 3)) == [1, 2, 3]   # পুরো পাক
assert to_list(rotate_right(build([1, 2, 3]), 0)) == [1, 2, 3]   # k = 0
assert to_list(rotate_right(build([]), 1)) == []                 # খালি
assert to_list(rotate_right(build([7]), 99)) == [7]              # একটা node
print("সব test pass!")

16. Line-by-line code explanation

  • if not head or not head.next: — খালি বা একক-node list rotate-এ অপরিবর্তিত।
  • length-loop — tail-এ পৌঁছানো পর্যন্ত হেঁটে length গোনো; শেষে tail শেষ node-এ।
  • k %= length — k-কে [0, L) সীমায় আনো; k == 0 হলে কিছুই না, head ফেরাও।
  • tail.next = head — list-কে একটা বৃত্তে বদলাও।
  • steps = length - k - 1 — new tail সামনে থেকে এতটা দূরে; এক loop-এ সেখানে যাও।
  • new_head = new_tail.next; new_tail.next = None — নতুন head ধরো, বৃত্ত কেটে list সোজা করো।

17. Output walkthrough

build([0,1,2]), k=4 → length 3, tail node 2। k = 4 % 3 = 1। ring: 2.next=0। steps = 1, new_tail = node 1, new_head = node 2। 1.next=None। ফল 2 -> 0 -> 1 → [2,0,1] — assert pass। বড় k, পুরো-পাক k, k=0, খালি, একক — সব pass; শেষে print: সব test pass!।

18. Time complexity

O(n) — একবার length/tail-এর জন্য হাঁটা, আরেকবার new tail-এ পৌঁছাতে আংশিক হাঁটা; মোট রৈখিক।

19. Space complexity

O(1) — শুধু কয়েকটা pointer আর একটা counter; list-এর সাইজের সাথে extra memory বাড়ে না।

20. Common mistakes

  • k %= length না করা — বড় k-তে হয় ভুল ফল, নয়তো অপ্রয়োজনীয় অসংখ্য ঘোরা।
  • steps ভুল গোনা — L - k বনাম L - k - 1 গুলিয়ে ফেলা; new_tail-কে এক ঘর বেশি/কম নিয়ে যাওয়া।
  • ring কাটতে ভুলে যাওয়া (new_tail.next = None) — তখন list-এ cycle থেকে যায়, to_list infinite loop।
  • খালি list বা head.next is None আলাদা করে না ভাবা — length-loop বা modulo-তে সমস্যা।

21. Which basic problem this inherits from

ভিত্তি: runner/gap চিন্তা (009-remove-nth-from-end.md — শেষ থেকে গুনে জায়গা ঠিক করা) আর modular arithmetic (math fundamentals)। আটকে গেলে "শেষ থেকে k-তম কোথায়" — এই প্রশ্নে ফিরে যাও।

22. Similar harder problems

23. Pattern learned

Close-the-ring + modular cut: list-কে বৃত্ত বানিয়ে k % L দিয়ে সঠিক জায়গায় কাটা — rotation-জাতীয় problem-এর সাফসুতরো কৌশল।

24. Final summary

ভবিষ্যতের আমাকে: "rotate দেখলে — length মাপো, k %= L করো, লেজ-মাথা জুড়ে ring বানাও, L-k-1 ঘর গিয়ে কাটো।" বারবার ঘোরানো নয়, একটা বৃত্ত একবার কাটা।

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