[Go版]算法通关村第二关青铜——终于学会链表反转了

这篇具有很好参考价值的文章主要介绍了[Go版]算法通关村第二关青铜——终于学会链表反转了。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目:反转链表

题目链接:LeetCode-206. 反转链表
[Go版]算法通关村第二关青铜——终于学会链表反转了,算法与数据结构,golang,算法,链表

解决方法

源码地址: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数据之后再做变更指向操作。

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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法通关村第二关——链表反转

    链表反转,就是链表原来是1-2-3-4-5,经过反转处理过后变成5-4-3-2-1 处理链表反转,有两种方式,一个是建立虚拟头结点,一个是直接操作链表反转。  这是执行的流程 最核心的两行就是 直接想我要让她反转,我现在设立了虚拟头结点,那我就要让新加进这个反转链表的结点

    2024年02月13日
    浏览(37)
  • [Go版]算法通关村第一关青铜——链表青铜挑战笔记

    单向链表图示: 双向链表图示: 环形单向链表图示: 环形双向链表图示: 源码地址: GitHub-golang版本 如果是单向的,需要将当前节点 定位到要插入节点的前一个节点 ,否则一旦过了将无法回头找到前一个节点 如果是双向的,将当前节点 定位到要插入节点的前一个节点、

    2024年02月13日
    浏览(40)
  • [Go版]算法通关村第一关——链表青铜挑战笔记

    单向链表图示: 双向链表图示: 环形单向链表图示: 环形双向链表图示: 源码地址: GitHub-golang版本 如果是单向的,需要将当前节点 定位到要插入节点的前一个节点 ,否则一旦过了将无法回头找到前一个节点 如果是双向的,将当前节点 定位到要插入节点的前一个节点、

    2024年02月15日
    浏览(46)
  • 算法通关村第二关——单链表加一

    LeetCode369 用一个非空单链表来表示一个非负整数,然后将这个整数加一。你可以假设这个整数除了 0 本身,没有任何前导的 0.这个证书的各个数位按照 高位在链表头部、低位在链表尾部 的顺序排列。 计算是从低位开始的,而链表是从高位开始的,所以要处理就必须反转过来

    2024年02月14日
    浏览(44)
  • 算法通关村|青铜挑战----链表

    前言:数据结构的基础:创建+增删改查 学习目标:单链表的创建+增删改查,双链表的创建+增删改查 数据域+指针域 数据域:当前节点的元素值 指针域:当前节点保存的下一个节点的元素的地址,其中最后一个元素的指针域指向null 标准的面向对象的节点的定义: LeetCode中节

    2024年02月15日
    浏览(36)
  • 算法通关村第二关——指定区间反转问题解析

    Leetcode92有这样一道题:给你单链表的头指针head和两个整数left、right,其中left=right,请你反转从位置left到位置right的链表结点,返回反转后的链表,如图所示: 这道题呢,有两种不同的解法,分别是头插法和穿针引线法,头插法就是我们前面说过的带头结点的反转,而穿针引

    2024年02月14日
    浏览(44)
  • 算法通关村第二关——K个一组反转

    前面有很多关于链表反转的知识,K个一组反转,就是让很多组节点进行翻转,本质也都是一样的。 现在的链表是 3-2-1-4-5-6-7-8 3-2-1已经进行了反转,现在要进行反转的是4-5-6 在这里首先计算出链表的长度,然后计算出要反转几组,现在定义pre为dummyNode,cur定义为head。 通过f

    2024年02月14日
    浏览(45)
  • 算法通关村第一关-链表青铜挑战笔记

    平时我们一般都是用数组,每个数组都会有一个相对应的索引,这样就使得数组能够方便的调用出对应索引得到需要的数据,但是这也造成了一个问题,那就是不好在数组中插入或者删除一个数据,例如 int arr[]={1,2,4,5}如果我想在数组中的2和4中添加一个数据3 那么我们首先就

    2024年02月15日
    浏览(43)
  • 算法通关村第一关——链表青铜挑战笔记

    链表的基本单元就是 节点 ,也就是说链表是由一个一个节点构成的。 而对于节点来说,里面至少会包含一个 指针 和一个 数据元素 ,也就是如下图所示: 其中数据域用来存放数据元素,指针域用来存放指向下一个节点的指针,这样一个一个连接起来的就是链表。如下图所

    2024年02月16日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包