Maison  >  Article  >  développement back-end  >  Un article explique comment implémenter une liste chaînée inversée dans Golang

Un article explique comment implémenter une liste chaînée inversée dans Golang

藏色散人
藏色散人avant
2021-07-19 14:37:002983parcourir

Problème : Inverser une liste à chaînage unique.

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

Tout d'abord, apprenons à connaître la structure des données de la liste chaînée :

Il y a deux éléments dans le nœud de la liste chaînée :

  • value
  • Pointeur
type ListNode struct {
    Val  int
    Next *ListNode
}

Pointe suivant vers le nœud suivant

Donc cette question est en fait Le pointeur pointe vers le nœud précédent

位置调换次数 pre cur whole
0 nil 1->2->3->4->5 1->2->3->4->5
1 1->nil 2->-3>->4->5 2->3->4->5->1->nil
2 2->1->nil 3->4->5 3->4->5->2->1->nil
3 3->2->1->nil 4->5 4->5->3->2->1->nil
4 4->3->2->1->nil 5 5->4->3->2->1->nil

On peut voir que

  • pre est l'avant de cur (pre = cur)
  • cur est l'élément de liste chaînée derrière la position actuelle (cur = cur.Next)
  • cur.Next est sûr Il est connecté à pre (cur.Next = pre)
Code complet :
package main

import "fmt"

//链表节点
type ListNode struct {
    Val  int
    Next *ListNode
}

//反转链表的实现
func reversrList(head *ListNode) *ListNode {
    cur := head
    var pre *ListNode = nil
    for cur != nil {
        pre, cur, cur.Next = cur, cur.Next, pre //这句话最重要
    }
    return pre
}

func main() {
    head := new(ListNode)
    head.Val = 1
    ln2 := new(ListNode)
    ln2.Val = 2
    ln3 := new(ListNode)
    ln3.Val = 3
    ln4 := new(ListNode)
    ln4.Val = 4
    ln5 := new(ListNode)
    ln5.Val = 5
    head.Next = ln2
    ln2.Next = ln3
    ln3.Next = ln4
    ln4.Next = ln5

    pre := reversrList(head)
    fmt.Println(pre)
}

Pour plus d'articles techniques liés au golang, veuillez visiter la colonne golangtutoriel !

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!

Déclaration:
Cet article est reproduit dans:. en cas de violation, veuillez contacter admin@php.cn Supprimer