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