Comment inverser la liste chaînée dans Golang

L'inversion des listes chaînées est une question courante et est souvent mentionnée dans les entretiens de programmation. Il s’agit d’un problème algorithmique classique largement utilisé et qui peut être utilisé pour inverser rapidement l’ordre d’une liste chaînée. Cet article présentera l'algorithme et les étapes pour implémenter une liste chaînée inversée en utilisant le langage Golang.

1. Définir des nœuds de liste chaînée unique

Avant de commencer à implémenter la liste chaînée inversée, nous devons définir un nœud de liste chaînée unique. Un nœud contient deux parties très importantes : le champ de données et le champ de pointeur. Le champ de données est utilisé pour stocker la valeur du nœud et le champ de pointeur est utilisé pour pointer vers le nœud suivant.

En Golang, nous pouvons utiliser la structure struct pour définir un nœud de liste à chaînage unique. La structure contient deux attributs : Val, utilisé pour représenter la valeur du nœud actuel, et Next, utilisé pour représenter le pointeur vers le nœud suivant.

type ListNode struct {

Val  int
Next *ListNode

}

2. Inversion de liste chaînée unique

Maintenant que nous avons défini les nœuds de la liste chaînée unique, l'étape suivante consiste à implémenter l'algorithme d'inversion de la liste chaînée. La clé pour inverser une liste chaînée est de parcourir la liste chaînée et de changer le pointeur vers chaque nœud.

Nous pouvons parcourir chaque nœud de la liste chaînée depuis le début et modifier tour à tour leurs pointeurs "Suivant" pour pointer vers le nœud précédent. De cette façon, la liste chaînée peut être inversée.

Les étapes de l'algorithme pour inverser la liste chaînée sont les suivantes :

(1) Définir deux pointeurs : pre et cur, pointant respectivement vers le premier nœud et le deuxième nœud. pre est le nœud précédent et cur est le nœud actuel.

(2) Parcourez la liste chaînée et pointez le pointeur Suivant du nœud actuel vers le nœud précédent pré.

(3) Déplacez le pointeur vers l'arrière, pointant pre vers le nœud actuel et cur vers le nœud suivant.

(4) Répétez les étapes 2 et 3 jusqu'à ce que toute la liste chaînée soit parcourue.

Le code d'implémentation est le suivant :

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. Code de test pour la liste chaînée inversée

Afin de vérifier l'exactitude de la liste chaînée inversée, nous écrivez du code de test à exécuter.

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. Inverser une partie de la liste chaînée

En plus d'inverser toute la liste chaînée, nous pouvons également inverser une partie de la liste chaînée. Par exemple, inversez la pièce du nœud m au nœud n dans la liste chaînée. Nous avons juste besoin d'apporter de légères modifications basées sur l'inversion de l'intégralité de la liste chaînée.

Nous pouvons d'abord traverser jusqu'au m-1ème nœud, le pré-pointeur pointe vers ce nœud et cur pointe vers le m-ème nœud. Ensuite, nous effectuons les étapes d’inversion de la liste chaînée jusqu’à revenir au nième nœud.

Le code d'implémentation est le suivant :

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. Le code de test pour inverser la liste chaînée partielle

Afin de vérifier Pour vérifier l'exactitude de l'inversion de la liste chaînée partielle, nous écrivons du code de test pour vérifier.

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. Résumé

Dans cet article, nous utilisons golang pour implémenter l'algorithme de liste chaînée inversée, notamment en inversant l'intégralité de la liste chaînée et en inversant une partie du lien liste. Inverser une liste chaînée est une question d’entretien courante et constitue également un algorithme de base pour résoudre les problèmes liés aux listes chaînées. Si vous êtes intéressé par les algorithmes de listes chaînées, il est recommandé d'étudier en profondeur d'autres algorithmes liés aux listes chaînées, tels que les pointeurs rapides et lents, les listes chaînées circulaires, la suppression de nœuds, etc.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!