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
以上是Reverse a linked list in go的详细内容。更多信息请关注PHP中文网其他相关文章!