Golang实现反转单链表

预期结果

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

实现原理介绍

首先先认识一下链表这个数据结构:

链表节点中有两个元素:

  • 指针
type Node struct {
	Data int
	Next *Node
}

Next指向下一个节点

Golang实现反转单链表

那么这个问题其实就是把指针指向前一个节点

位置调换次数precurwhole
0nil1->2->3->4->51->2->3->4->5
11->nil2->-3>->4->52->3->4->5->1->nil
22->1->nil3->4->53->4->5->2->1->nil
33->2->1->nil4->54->5->3->2->1->nil
44->3->2->1->nil55->4->3->2->1->nil

可以看出来

  • pre是cur的最前面那位(pre = cur)
  • cur就是当前位的后面链表元素(cur = cur.Next)
  • cur.Next肯定是接pre(cur.Next = pre)

完整代码

package main

import "fmt"

/*
  @Author : lanyulei
  @Desc : 反转单链表
*/

type Node struct {
	Data int
	Next *Node
}

func reversal(head *Node) *Node {
	cur := head
	var pre *Node = nil
	for cur != nil {
		pre, cur, cur.Next = cur, cur.Next, pre
	}
	return pre
}

func main() {
	head := new(Node)
	head.Data = 0

	tail := head
	for i := 1; i < 10; i++ {
		tail.Next = &Node{
			Data: i,
			Next: nil,
		}

		tail = tail.Next
	}

	head = reversal(head)

	for {
		fmt.Println(head.Data)
		if head.Next == nil {
			break
		}
		head = head.Next
	}
}

参考

https://www.cnblogs.com/TimLiuDream/p/9932494.html

本文为原创文章,未经授权禁止转载本站文章。
原文出处:兰玉磊的个人博客
原文链接:https://www.fdevops.com/2021/05/20/go-30766
版权:本文采用「署名-非商业性使用-相同方式共享 4.0 国际」知识共享许可协议进行许可。

(3)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2021年4月24日 18:15
下一篇 2021年5月29日 21:53

相关推荐

发表评论

您的电子邮箱地址不会被公开。

评论列表(2条)