Golang senarai terpaut separa terbalik

Menterbalikkan senarai terpaut adalah masalah klasik, ia digunakan secara meluas, kerumitan masa tidak tinggi, dan ia tidak sukar untuk dilaksanakan. Artikel ini akan memperkenalkan cara melaksanakan algoritma untuk membalikkan senarai terpaut separa dalam golang.

Terbalikkan senarai terpaut

Mari kita lihat cara membalikkan senarai terpaut Kita boleh melaksanakannya dalam dua cara: lelaran atau rekursi.

1. Kaedah berulang

Kami menggunakan tiga penunjuk pra, cur dan seterusnya secara berulang melakukan operasi pembalikan, di mana pra dan seterusnya adalah untuk menyimpan pendahulu dan pengganti nod cur untuk penyambungan semula yang mudah selepas pembalikan. Kodnya adalah seperti berikut:

func reverseList(head *ListNode) *ListNode {
    var pre *ListNode = nil
    cur := head
    for cur != nil {
        next := cur.Next
        cur.Next = pre
        pre = cur
        cur = next
    }
    return pre
}

2. Kaedah rekursif

Walaupun kaedah rekursif tidak semudah difahami sebagai kaedah berulang, ia sebenarnya merupakan contoh yang baik untuk berlatih pemikiran rekursif. Apa yang perlu diperhatikan dalam operasi rekursif ialah selepas mengulangi ke penghujung senarai terpaut, nod ekor perlu diberikan kepada nod Seterusnya kepala, dan kemudian nod ekor dikembalikan sebagai kepala baharu. Kodnya adalah seperti berikut:

func reverseListRecursive(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    newHead := reverseListRecursive(head.Next)
    head.Next.Next = head
    head.Next = nil
    return newHead
}

Senarai terpaut separa terbalik

Dengan asas membalikkan senarai terpaut, mari kita lihat cara membalikkan senarai terpaut separa. Penerangan masalah adalah seperti berikut:

Memandangkan senarai terpaut dan dua integer m dan n, balikkan senarai terpaut dari kedudukan m ke n. Ia diperlukan untuk memberikan pelaksanaan algoritma.

Dengan memerhati soalan, kita boleh membahagikannya kepada tiga bahagian untuk dipertimbangkan:

1. Sebelum m: Tidak perlu membalikkan senarai terpaut
2. m ke n Antara: Perlu membalikkan senarai terpaut
3. n Selepas: Tidak perlu membalikkan senarai terpaut

Oleh itu, kita perlu menggunakan pembolehubah pra dan ekor untuk merekodkan nod ekor bagi bahagian pertama dan bahagian kedua Nod kepala, dan kemudian terbalikkan bahagian kedua Selepas membalikkan, sambungkan nod ekor bahagian pertama dan nod kepala bahagian kedua.

Kodnya adalah seperti berikut:

func reverseBetween(head *ListNode, m int, n int) *ListNode {
    if head == nil || m <= 0 || n < m {
        return head
    }
    
    // 特判，如果m=1，则不需要第一部分
    if m == 1 {
        return reverseN(head, n)
    }
    
    //  遍历到m-1位置，记录pre和tail
    var pre *ListNode = nil
    cur := head
    for i := 1; i < m; i++ {
        pre = cur
        cur = cur.Next
    }

    tail := cur // tail 记录第一部分的末尾是 cur             
    // 将第二部分进行反转操作
    new_head := reverseN(cur, n - m + 1)

    // 将第一部分与第二部分重新连接
    tail.Next = new_head
    if pre != nil {
        pre.Next = tail
        return head
    } else {
        return tail
    }
}

// 反转前n个节点
func reverseN(head *ListNode, n int) *ListNode {
    if head == nil || n <= 0 {
        return head
    }
    if n == 1 {
        return head
    }
    var pre *ListNode = nil
    cur := head
    for i := 1; i <= n && cur != nil; i++ {
        next := cur.Next
        cur.Next = pre
        pre = cur
        cur = next
    }
    head.Next = cur
    return pre
}

Ringkasan

Senarai pautan terbalik ialah pelawat kerap soalan temuduga senarai terpaut ini bukan sahaja dapat menyelesaikan masalah senarai terpaut terbalik, tetapi juga mengembangkan operasi Transform kepada senarai terpaut lain. Semasa menjalankan temu bual, senarai pautan terbalik boleh digunakan sebagai contoh untuk soalan lain, yang sangat penting untuk mengembangkan idea. Untuk melaksanakan senarai pautan terbalik dan algoritma senarai terpaut separa dalam golang, anda perlu memberi perhatian kepada penggunaan penunjuk, Penghakiman Nil dan isu-isu lain Selepas menguasai kod, ia adalah sangat mudah untuk dilaksanakan.

Atas ialah kandungan terperinci Golang senarai terpaut separa terbalik. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!