输出反向链接列表时出现无限循环

Question

I'm learning Go and have written the following code to reverse a linked list. However, the code doesn't work as expected.

Here's a Node structure along with the function for printing and reversing the list.

type Node struct {
    number   int
    previous *Node
    next     *Node
}

func PrintList(node *Node) {
    for n := node; n != nil; n = n.next {
        fmt.Println(n)
    }
}

func ReverseList(node *Node) {
    var nextNodeRef *Node

    for n := node; n != nil; n = n.previous {
        if n.next == nil {
            n.next = n.previous
            n.previous = nil

            *node = *n

            break
        } else {
            nextNodeRef = n.next

            n.next = n.previous
            n.previous = nextNodeRef

            if n.next == nil {
                node = n
            }
        }
    }

}

The problem is that when I reverse the list and call PrintList I get a seemingly infinite output of all the elements of the list except for the last one (which used to be the first element)

Here's my main function:

func main() {
    myList := Node{1, nil, nil}
    myListAddress := &myList

    AddNumber(2, myListAddress)
    AddNumber(3, myListAddress)

    fmt.Println("My list:")
    PrintList(myListAddress)

    ReverseList(myListAddress)
    fmt.Println("My list reversed:")
    // here I always get list elements that contain 3, 2, 3, 2...
    PrintList(myListAddress)
}

And here's the AddNumber function that I use:

func AddNumber(number int, node *Node) *Node {
    if node == nil {
        log.Fatal("No Node provided")
    }

    var newNode Node

    for n := node; n != nil; n = n.next {
        if n.next == nil {
            newNode = Node{number, n, nil}
            n.next = &newNode

            break
        }
    }

    return &newNode
}

Answer 1

*node = *n

This line does not do what you think it does. You probably hoped it'd change that outer *Node to point to the new head (old tail), yes? Well no, it simply replaces the node at that location. Which explains why the former first value is missing.

So before this last step you have something like this

nil <- 3 <=> 2 <=> 1 -> nil
       ↑           ↑
       n           node, myListAddress

Then you replace node with value of n (which is nil <- 3 -> 2). This makes the structure look like this:

      prev
 ┌────────────────┐
 │                │ node, myListAddress    
 ˅                │╱
nil <- 3 <=> 2 -> 3 ──┐
             ^        │next
             └────────┘

By the way, this list is so small that this diagram may be misleading. Here's how it looks with more elements:

      prev
 ┌────────────────────────────┐
 │                            │ node, myListAddress    
 ˅                            │╱
nil <- 5 <=> 4 <=> 3 <=> 2 -> 5 ──┐
             ^                    │next
             └────────────────────┘

You can either use a **Node there. Or simply return the new head from the function:

func ReverseList(node *Node) *Node {

    for n := node; n != nil; n = n.previous {
        if n.next == nil {
            n.next = n.previous
            n.previous = nil

            return n
        } else {
            n.next, n.previous = n.previous, n.next
        }
    }

    return node
}

Then

myListAddress = ReverseList(myListAddress)