حذف گره میانی یک لیست پیوندی

شما باید گره میانی را از یک لیست پیوندی تک‌گوشی حذف کنید. گره میانی، با استفاده از ایندکس‌گذاری مبتنی بر صفر، گره ⌊n / 2⌋-ام است.

در اینجا روش حل کارآمد آن آمده است.

استراتژی

از دو اشاره‌گر برای یافتن میانه در یک پیمایش استفاده کنید.

منطق

  1. حالت‌های خاص را مدیریت کنید. اگر لیست تنها یک گره دارد، null را برگردانید.
  2. اشاره‌گرهای slow و fast را در گره سر (head) مقداردهی اولیه کنید.
  3. اشاره‌گر fast را دو گام و اشاره‌گر slow را یک گام حرکت دهید.
  4. یک اشاره‌گر prev را به‌روزرسانی کنید تا یک گام پشت سر اشاره‌گر slow باقی بماند.
  5. پس از پایان حلقه، گره prev را به گره بعد از slow متصل کنید. این کار گره میانی را حذف می‌کند.

پیچیدگی

پیاده‌سازی PHP

function deleteMiddle(ListNode $head): ?ListNode
{
    if ($head->next == null) {
        return null;
    }

    $slow = $head;
    $fast = $head;
    $prev = null;

    while ($fast !== null && $fast->next !== null) {
        $prev = $slow;
        $slow = $slow->next;
        $fast = $fast->next->next;
    }

    $prev->next = $slow->next;

    return $head;
}

منبع: https://dev.to/mdarifulhaque/2095-delete-the-middle-node-of-a-linked-list-4jf1