This is a favorite question to give to new developers. Pretty simple if you have had a decent data structures class.
Reverse a single linked list.
For the implementation, I have chosen to make the linked list a generic type.
Data T
Next *Node[T]
}
type LinkedList[T any] struct {
Head *Node[T]
}
func (ll *LinkedList[T]) Append(data T) {
newNode := &Node[T]{Data: data, Next: nil}
if ll.Head == nil {
ll.Head = newNode
return
}
current := ll.Head
for current.Next != nil {
current = current.Next
}
current.Next = newNode
}
And for the reverse function, it’s done with a single pass by recognizing that all we need to do is maintain a pointer to the previous node, then set a given node’s ‘next’ to the previous.
When we reach the end, then we know the current node is the new ‘head’ of the list.
var prev *Node[T] = nil
var ptr *Node[T] = ll.Head
for ptr != nil {
var next *Node[T] = ptr.Next
ptr.Next = prev
prev = ptr
if next == nil {
ll.Head = ptr
}
ptr = next
}
}
Have we missed a boundary condition? What complications are added if the list is now a doubly linked list? Let me know in the comments.
Thanks!
The code for this post and all posts in this series can be found here
![[15/52] The Three Languages an Engineer Needs To Know (or maybe it’s more)](https://media.dev.to/cdn-cgi/image/width=800%2Cheight=%2Cfit=scale-down%2Cgravity=auto%2Cformat=auto/https%3A%2F%2Fdev-to-uploads.s3.amazonaws.com%2Fuploads%2Farticles%2F7zx0rh5uggp9bnn878y0.png)
