Alih keluar Nth daripada hujung senarai terpaut

Dalam siaran ini, saya meneroka algoritma senarai terpaut yang lain. Yang ini lebih sukar.

Buat fungsi untuk mengalih keluar nod ke-n dari hujung senarai terpaut.

Ini datang daripada masalah leetcode. Seperti dalam masalah leetcode, 'n' adalah berasaskan satu dan boleh pergi dari 1 ke panjang senarai.

func (ll *LinkedList[T]) RemoveNthFromEnd(n int) *Node[T] {
    if n == 0 {
        return nil
    }
    fast := ll.Head // this moves to the end
    slow := ll.Head // this should be one behind the nth from end

    for count := 0; count < n; count++ {
        if fast == nil { // list is too short
            return nil
        }
        fast = fast.Next
    }
    if fast == nil { // special case, removing head
        res := ll.Head
        ll.Head = ll.Head.Next
        return res
    }
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next
    }
    res := slow.Next
    slow.Next = slow.Next.Next
    return res
}

Kunci untuk ini ialah menggunakan dwi penunjuk. Kita mulakan dengan memulakan penunjuk cepat dan perlahan ke kepala senarai.

Seterusnya, kami menggerakkan penunjuk n nod pantas ke hadapan. Dengan cara ini, penunjuk perlahan kini 'n' di belakang penunjuk pantas. Sekarang, kita boleh menggerakkan kedua-dua penunjuk dalam langkah kunci sehingga pantas berada di penghujung.

Kami kemudian boleh mengalih keluar nod ke-n ke terakhir dan mengembalikannya.

Adakah cara yang lebih baik? Beritahu saya dalam ulasan.

Terima kasih!

Kod untuk siaran ini dan semua siaran dalam siri ini boleh didapati di sini

Atas ialah kandungan terperinci Alih keluar Nth daripada hujung senarai terpaut. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!