输出反向链表时获得无限循环

Question

我正在学习Go，并编写了以下代码来反转链表。但是，代码无法按预期工作。

这是一个节点结构以及用于打印和反转列表的函数。

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
            }
        }
    }
}

问题是，当我反转列表并调用PrintList时，我得到了列表中所有元素的看似无限的输出，除了最后一个元素(曾经是第一个元素(

这是我的main函数：

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)
}

这是我使用AddNumber函数：

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

这条线没有做你认为它做的事情。您可能希望它会改变外部*Node以指向新头(旧尾巴(，是吗？好吧，不，它只是替换该位置的节点。这就解释了为什么缺少前一个值。

所以在最后一步之前，你有这样的东西

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

然后，将node替换为 n 的值(即 nil <- 3 -> 2 (。这使得结构看起来像这样：

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

顺便说一下，这个列表太小了，这个图可能会产生误导。以下是更多元素的外观：

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

您可以在那里使用**Node。或者只是从函数中返回新头：

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
}

然后

myListAddress = ReverseList(myListAddress)