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. (This is Leetcode 206)
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
Top comments (0)