预期结果
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL实现原理介绍
首先先认识一下链表这个数据结构：
链表节点中有两个元素：
- 值
- 指针
type Node struct {
Data int
Next *Node
}Next指向下一个节点
那么这个问题其实就是把指针指向前一个节点
| 位置调换次数 | pre | cur | whole |
|---|---|---|---|
| 0 | nil | 1->2->3->4->5 | 1->2->3->4->5 |
| 1 | 1->nil | 2->-3>->4->5 | 2->3->4->5->1->nil |
| 2 | 2->1->nil | 3->4->5 | 3->4->5->2->1->nil |
| 3 | 3->2->1->nil | 4->5 | 4->5->3->2->1->nil |
| 4 | 4->3->2->1->nil | 5 | 5->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
}
}