Liste chaînée partielle inversée golang

Inverser une liste chaînée est un problème classique, il est largement utilisé, la complexité temporelle n'est pas élevée et ce n'est pas difficile à mettre en œuvre. Cet article présentera comment implémenter un algorithme pour inverser une liste chaînée partielle dans Golang.

Inverser la liste chaînée

Voyons d'abord comment inverser la liste chaînée. Nous pouvons l'implémenter de deux manières : par itération ou par récursivité.

1. Méthode itérative

Nous utilisons trois pointeurs pre, cur et next pour effectuer de manière itérative l'opération d'inversion Pre et next pour enregistrer les nœuds prédécesseur et successeur de cur afin de faciliter la reconnexion après l'inversion. Le code est le suivant :

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. Méthode récursive

Bien que la méthode récursive ne soit pas aussi facile à comprendre que la méthode itérative, c'est en fait un bon exemple de pratique de la pensée récursive. Ce qu'il faut noter dans l'opération récursive, c'est qu'après une récursion jusqu'à la fin de la liste chaînée, le nœud de queue doit être attribué au nœud suivant de la tête, puis le nœud de queue est renvoyé en tant que nouvelle tête. Le code est le suivant :

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
}

Inverser la liste chaînée partielle

Avec la base de l'inversion de la liste chaînée, voyons comment inverser la liste chaînée partielle. La description du problème est la suivante :

Étant donné une liste chaînée et deux entiers m et n, inversez la liste chaînée de la position m à n. Il est nécessaire de donner une implémentation d’algorithme.

En observant la question, nous pouvons la diviser en trois parties pour examen :

1. Avant : pas besoin d'inverser la liste chaînée
2. Entre m et n : nécessité d'inverser la liste chaînée
3. Après n : pas besoin de liste chaînée de transfert inversé

Par conséquent, nous devons utiliser des variables pré et queue pour enregistrer le nœud de queue de la première partie et le nœud de tête de la deuxième partie, puis inverser la deuxième partie après l'inversion, le nœud de queue de. la première partie et le nœud principal de la deuxième partie sont simplement connectés les nœuds principaux des deux parties.

Le code est le suivant :

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
}

Résumé

L'inversion des listes chaînées est une question fréquente dans les questions d'entretien sur les listes chaînées. La maîtrise de cette idée algorithmique peut non seulement résoudre le problème de l'inversion des listes chaînées, mais également s'étendre à d'autres transformations de listes chaînées. opérations. Lors des entretiens, la liste chaînée inversée peut être utilisée comme exemple pour d’autres questions, ce qui est très important pour développer des idées. Pour implémenter les algorithmes de liste chaînée inversée et de liste chaînée partielle dans Golang, vous devez faire attention à l'utilisation de pointeurs, au jugement nul et à d'autres problèmes. Après avoir maîtrisé le code, c'est très simple à mettre en œuvre.

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!