Umgekehrte teilweise verknüpfte Liste Golang

Das Umkehren einer verknüpften Liste ist ein klassisches Problem, es wird häufig verwendet, die zeitliche Komplexität ist nicht hoch und es ist nicht schwer zu implementieren. In diesem Artikel wird vorgestellt, wie ein Algorithmus zum Umkehren einer teilweise verknüpften Liste in Golang implementiert wird.

Umkehren der verknüpften Liste

Sehen wir uns zunächst an, wie man die verknüpfte Liste umkehrt. Wir können es auf zwei Arten implementieren: Iteration oder Rekursion.

1. Iterationsmethode

Wir verwenden drei Zeiger pre, cur und next, um die Umkehroperation iterativ durchzuführen. Pre und next dienen dazu, die Vorgänger- und Nachfolgerknoten von cur zu speichern, um die erneute Verbindung nach der Umkehrung zu erleichtern. Der Code lautet wie folgt:

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. Rekursive Methode

Obwohl die rekursive Methode nicht so einfach zu verstehen ist wie die iterative Methode, ist sie tatsächlich ein gutes Beispiel für die Ausübung rekursiven Denkens. Bei der rekursiven Operation ist zu beachten, dass nach der Rekursion zum Ende der verknüpften Liste der Endknoten dem nächsten Knoten des Kopfes zugewiesen werden muss und der Endknoten dann als neuer Kopf zurückgegeben wird. Der Code lautet wie folgt:

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
}

Teilweise verknüpfte Liste umkehren

Auf der Grundlage der Umkehrung der verknüpften Liste werfen wir einen Blick darauf, wie die teilweise verknüpfte Liste umgedreht wird. Die Beschreibung des Problems lautet wie folgt:

Gegeben eine verknüpfte Liste und zwei ganze Zahlen m und n, kehren Sie die verknüpfte Liste von Position m nach n um. Es ist erforderlich, eine Algorithmusimplementierung anzugeben.

Durch Beobachtung der Frage können wir sie zur Betrachtung in drei Teile aufteilen:

1. Vorher: Keine Notwendigkeit, die verknüpfte Liste umzukehren.
2. Zwischen m und n: Notwendigkeit, die verknüpfte Liste umzukehren.
3. Nach n: Keine Notwendigkeit Verknüpfte Liste umgekehrt übertragen

Daher müssen wir Pre- und Tail-Variablen verwenden, um den Tail-Knoten des ersten Teils und den Head-Knoten des zweiten Teils aufzuzeichnen, und dann den Tail-Knoten des zweiten Teils umkehren Der erste Teil und der Kopfknoten des zweiten Teils sind einfach die Kopfknoten der beiden Teile verbinden.

Der Code lautet wie folgt:

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
}

Zusammenfassung

Das Umkehren verknüpfter Listen ist eine häufige Frage in Interviewfragen zu verknüpften Listen. Die Beherrschung dieser algorithmischen Idee kann nicht nur das Problem des Umkehrens verknüpfter Listen lösen, sondern auch auf andere Transformationen verknüpfter Listen ausgedehnt werden Operationen. Bei der Durchführung von Interviews kann die invertierte verknüpfte Liste als Beispiel für andere Fragen verwendet werden, was für die Ideenentwicklung sehr wichtig ist. Um die Algorithmen für umgekehrt verknüpfte Listen und teilweise verknüpfte Listen in Golang zu implementieren, müssen Sie auf die Verwendung von Zeigern, die Nullbeurteilung und andere Probleme achten. Nach der Beherrschung des Codes ist die Implementierung sehr einfach.

Das obige ist der detaillierte Inhalt vonUmgekehrte teilweise verknüpfte Liste Golang. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!