So kehren Sie verknüpfte Listen in Golang um

Das Umkehren verknüpfter Listen ist eine häufig gestellte Frage und wird häufig in Programmierinterviews erwähnt. Es handelt sich um ein klassisches Algorithmusproblem, das weit verbreitet ist und zum schnellen Umkehren der Reihenfolge einer verknüpften Liste verwendet werden kann. In diesem Artikel werden der Algorithmus und die Schritte zum Implementieren einer umgekehrt verknüpften Liste mithilfe der Golang-Sprache vorgestellt.

1. Einfach verknüpfte Listenknoten definieren

Bevor wir mit der Implementierung der umgekehrt verknüpften Liste beginnen, müssen wir einen einfach verknüpften Listenknoten definieren. Ein Knoten enthält zwei sehr wichtige Teile: Datenfeld und Zeigerfeld. Das Datenfeld wird verwendet, um den Wert des Knotens zu speichern, und das Zeigerfeld wird verwendet, um auf den nächsten Knoten zu zeigen.

In Golang können wir die Strukturstruktur verwenden, um einen einfach verknüpften Listenknoten zu definieren. Die Struktur enthält zwei Attribute: Val, das zur Darstellung des Werts des aktuellen Knotens verwendet wird, und Next, das zur Darstellung des Zeigers auf den nächsten Knoten verwendet wird.

Typ ListNode struct {

Val  int
Next *ListNode

}

2. Umkehrung der einfach verknüpften Liste

Da wir nun die Knoten der einfach verknüpften Liste definiert haben, besteht der nächste Schritt darin, den Algorithmus zum Invertieren der verknüpften Liste zu implementieren. Der Schlüssel zum Umkehren einer verknüpften Liste besteht darin, die verknüpfte Liste zu durchlaufen und den Zeiger auf jeden Knoten zu ändern.

Wir können jeden Knoten in der verknüpften Liste von Anfang an durchlaufen und ihre „Weiter“-Zeiger der Reihe nach so ändern, dass sie auf den vorherigen Knoten zeigen. Auf diese Weise kann die verknüpfte Liste umgekehrt werden.

Die Algorithmusschritte zum Umkehren der verknüpften Liste lauten wie folgt:

(1) Definieren Sie zwei Zeiger: pre und cur, die jeweils auf den ersten Knoten und den zweiten Knoten zeigen. pre ist der vorherige Knoten und cur ist der aktuelle Knoten.

(2) Durchlaufen Sie die verknüpfte Liste und zeigen Sie mit dem Next-Zeiger des aktuellen Knotens auf den vorherigen Knoten vor.

(3) Bewegen Sie den Zeiger nach hinten und zeigen Sie pre auf den aktuellen Knoten und cur auf den nächsten Knoten.

(4) Wiederholen Sie die Schritte 2 und 3, bis die gesamte verknüpfte Liste durchlaufen ist.

Der Implementierungscode lautet wie folgt:

func reverseLinkedList(head ListNode) ListNode {

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

}

3. Testcode für umgekehrte verknüpfte Liste

Um die Richtigkeit der umgekehrt verknüpften Liste zu überprüfen, haben wir Schreiben Sie einen Testcode zur Ausführung.

func TestReverseLinkedList(t *testing.T) {

head := &ListNode{Val: 1}
node1 := &ListNode{Val: 2}
node2 := &ListNode{Val: 3}
node3 := &ListNode{Val: 4}
node4 := &ListNode{Val: 5}

head.Next = node1
node1.Next = node2
node2.Next = node3
node3.Next = node4

newHead := reverseLinkedList(head)

assert.Equal(t, newHead.Val, 5)
assert.Equal(t, newHead.Next.Val, 4)
assert.Equal(t, newHead.Next.Next.Val, 3)
assert.Equal(t, newHead.Next.Next.Next.Val, 2)
assert.Equal(t, newHead.Next.Next.Next.Next.Val, 1)

}

4. Teil der verknüpften Liste umkehren

Zusätzlich zum Umkehren der gesamten verknüpften Liste können wir auch einen Teil der verknüpften Liste umkehren. Kehren Sie beispielsweise den Teil von Knoten m zu Knoten n in der verknüpften Liste um. Wir müssen lediglich geringfügige Änderungen vornehmen, indem wir die gesamte verknüpfte Liste umkehren.

Wir können zuerst zum m-1-ten Knoten gehen, der Prä-Zeiger zeigt auf diesen Knoten und der Cur-Punkt zeigt auf den m-ten Knoten. Dann führen wir die Schritte zum Umkehren der verknüpften Liste durch, bis wir zum n-ten Knoten zurückkehren.

Der Implementierungscode lautet wie folgt:

func reverseBetween(head ListNode, m int, n int) ListNode {

dummy := &ListNode{0, head}
pre := dummy

for i := 1; i < m; i++ {
    pre = pre.Next
}

cur := pre.Next
for i := m; i < n; i++ {
    next := cur.Next
    cur.Next = next.Next
    next.Next = pre.Next
    pre.Next = next
}

return dummy.Next

}

5. Der Testcode zum Umkehren der teilweise verknüpften Liste

Zur Überprüfung Um die Richtigkeit der Umkehrung der teilweise verknüpften Liste zu überprüfen, schreiben wir einen Testcode, um dies zu überprüfen.

func TestReverseBetween(t *testing.T) {

head := &ListNode{Val: 1}
node1 := &ListNode{Val: 2}
node2 := &ListNode{Val: 3}
node3 := &ListNode{Val: 4}
node4 := &ListNode{Val: 5}

head.Next = node1
node1.Next = node2
node2.Next = node3
node3.Next = node4

newHead := reverseBetween(head, 2, 4)

assert.Equal(t, newHead.Val, 1)
assert.Equal(t, newHead.Next.Val, 4)
assert.Equal(t, newHead.Next.Next.Val, 3)
assert.Equal(t, newHead.Next.Next.Next.Val, 2)
assert.Equal(t, newHead.Next.Next.Next.Next.Val, 5)

}

6. Zusammenfassung

In diesem Artikel verwenden wir Golang, um den Algorithmus für umgekehrt verknüpfte Listen zu implementieren, einschließlich der Umkehrung der gesamten verknüpften Liste und der Umkehrung eines Teils der verknüpften Liste Liste. Das Umkehren einer verknüpften Liste ist eine häufig gestellte Frage in Vorstellungsgesprächen und auch ein grundlegender Algorithmus zur Lösung von Problemen im Zusammenhang mit verknüpften Listen. Wenn Sie sich für Algorithmen für verknüpfte Listen interessieren, wird empfohlen, dass Sie sich eingehend mit anderen Algorithmen für verknüpfte Listen befassen, z. B. schnelle und langsame Zeiger, zirkulär verknüpfte Listen, Löschen von Knoten usw.

Das obige ist der detaillierte Inhalt vonSo kehren Sie verknüpfte Listen in Golang um. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!