🎯 مسأله مصاحبه گوگل - شماره 1207

🎯 مسأله مصاحبه گوگل

فرض کنید یک لیست پیوندی (Singly Linked List) داریم و یک عدد صحیح k.
باید k‌اُمین عنصر از انتها را از لیست حذف کنیم.

🔒 محدودیت‌ها:

• k همیشه کوچک‌تر از طول لیست است.

• لیست خیلی طولانی است، پس نباید بیش از یک بار از ابتدا تا انتها پیمایش کنیم (یعنی فقط یک پاس).

• باید در فضای ثابت (O(1)) حل شود.

💡 ایده حل (تفکر الگوریتمی)

برای حل در یک پاس، تکنیک دو اشاره‌گر (Two Pointers) بهترین انتخاب است:

1. اشاره‌گر اول را k گام جلو می‌بریم.

2. سپس همزمان، اشاره‌گر اول و دوم را یک‌به‌یک جلو می‌بریم.

3. وقتی اشاره‌گر اول به آخر لیست برسد، اشاره‌گر دوم درست روی عنصر قبل از k‌اُمین از آخر خواهد بود.

4. کافی است لینک آن را طوری تغییر دهیم که عنصر موردنظر حذف شود.

🔎 پیاده‌سازی خط‌به‌خط (Python)

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

def remove_kth_from_end(head, k):
    # گام 1: ایجاد دو اشاره‌گر (fast و slow) هر دو در ابتدای لیست
    fast = slow = head
    
    # گام 2: حرکت fast به اندازه k گام جلو
    for _ in range(k):
        fast = fast.next
    
    # حالت خاص: اگر fast به None رسید یعنی باید head را حذف کنیم
    if not fast:
        return head.next
    
    # گام 3: حرکت همزمان fast و slow تا وقتی fast به آخر لیست برسد
    while fast.next:
        fast = fast.next
        slow = slow.next
    
    # گام 4: حذف عنصر kام از آخر با تغییر لینک slow
    slow.next = slow.next.next
    
    return head

✨ توضیح حرفه‌ای خط‌به‌خط

• fast = slow = head
  هر دو اشاره‌گر در ابتدای لیست قرار می‌گیرند.

• for _ in range(k): fast = fast.next
  اشاره‌گر سریع k قدم جلو می‌رود. حالا بین fast و slow فاصله‌ی k گره وجود دارد.

• if not fast: return head.next
  اگر fast به آخر رسید، یعنی باید عنصر اول (head) حذف شود.

• while fast.next:
  همزمان fast و slow را جلو می‌بریم تا fast به آخر برسد.

• slow.next = slow.next.next
  حالا slow درست قبل از گره هدف است. با تغییر لینک، گره هدف حذف می‌شود.

✅ خروجی نهایی

این الگوریتم در:

• یک پاس (O(n))

• فضای ثابت (O(1))
  لیست را پردازش کرده و عنصر kام از آخر را حذف می‌کند.

📌 این همان نوع مسأله‌ای است که در مصاحبه‌های شرکت‌هایی مثل گوگل می‌آید:
نه خیلی سخت، نه خیلی آسان؛ اما دقیقاً جایی که قدرت تفکر الگوریتمی ساده و بهینه را محک می‌زند.

Daily Coding Problem: Problem #1207 [Medium