题目:反转链表
题目链接:LeetCode-206. 反转链表
解决方法
源码地址:GitHub-golang版本
方法1:借助虚拟头节点反转
说明:遍历该链表,依次取出当前节点插入到新链表的首位(虚拟头结点紧后)即可,注意要提前保存当前节点的Next数据,否则插入到新链表后就没法继续向下遍历了。
func ReverselistByHead[T any](listNode *slink.LinkNode[T]) *slink.LinkNode[T]{
if listNode == nil || listNode.Next == nil {
return listNode
}
newHead := &slink.LinkNode[T]{}
// 第一个有值结点
tmp := listNode.Next
for {
next := tmp.Next
// 下面两步将tmp结点挂在到新链表的首位
tmp.Next = newHead.Next
newHead.Next = tmp
if next == nil {
break
}
tmp = next
}
return newHead
}
方法2:不借助虚拟头节点,仅靠自身反转
说明:原理和方法1一致,只不过现在没有虚拟头结点,所以每次遍历到的当前节点都将其的Next指向新链表,然后再让新链表的头节点变更为该节点(就是每次都给新链表变更头结点),同样注意要提前保存当前节点的Next数据之后再做变更指向操作。文章来源:https://www.toymoban.com/news/detail-635969.html
func ReverselistBySelf[T any](listNode *slink.LinkNode[T]) *slink.LinkNode[T] {
if listNode == nil || listNode.Next == nil {
return listNode
}
var newList *slink.LinkNode[T]
tmp := listNode
for {
next := tmp.Next
tmp.Next = newList
newList = tmp
if next == nil {
break
}
tmp = next
}
return newList
}
方法3:利用递归来反转
说明:递归思想是自身调用自身。这里要反转一个链表,就是先找到它的末尾节点,作为新链表的头节点,然后依次将其与其上一个节点的指向关系对换,即:
将 1->2->3->4->5->nil 中的 4->5->nil 对换成 5->4->nil,然后接着
3->4->nil对换成4->3->nil( 这里5的指向没有变,所以 5->4->3->nil )
2->3->nil对换成3->2->nil ( 这里4的指向没有变,所以 5->4->3->2->nil )
1->2->nil对换成2->1->nil ( 同理3的指向没有变,所以得到了 5->4->3->2->1->nil )文章来源地址https://www.toymoban.com/news/detail-635969.html
func ReverseListByRecursion[T any](listNode *slink.LinkNode[T]) *slink.LinkNode[T]{
if listNode == nil || listNode.Next == nil {
return listNode
}
tmp := listNode
// newList将是该链表的尾节点
newList := ReverseListByRecursion(tmp.Next)
// 将tmp和它的下一个交换(eg: 2->3 ==> 3->2)
tmp.Next.Next = tmp
tmp.Next = nil
return newList
}
到了这里,关于[Go版]算法通关村第二关青铜——终于学会链表反转了的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!