This content originally appeared on DEV Community and was authored by Johns Code
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.
type Node[T any] struct {
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.
func (ll *LinkedList[T]) ReverseLinkedList() {
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
This content originally appeared on DEV Community and was authored by Johns Code
Johns Code | Sciencx (2024-07-11T23:55:53+00:00) Reverse a linked list in go. Retrieved from https://www.scien.cx/2024/07/11/reverse-a-linked-list-in-go/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.