golang的链表结构简单,如下
type ListNode struct {
Val int //节点值
Next *ListNode //存储着下一个节点的地址,用指针表示
}
不废话,先定义并初始化一个单链表
func main() {
head := new(ListNode)
head.Val = 1
ln2 := new(ListNode)
ln2.Val = 2
ln3 := new(ListNode)
ln3.Val = 3
ln4 := new(ListNode)
ln4.Val = 4
ln5 := new(ListNode)
ln5.Val = 5
head.Next = ln2
ln2.Next = ln3
ln3.Next = ln4
ln4.Next = ln5
pre := reverse(head)
}
然后,开始介绍我所理解的方法
方法一:新建一个链表(只有头结点),然后遍历需要翻转的链表,逐个插入到新链表中即可,最后新链表就是原链表的翻转链表,如图
图例解释:
1、dummy是只有头结点的新链表,或者说dummy就是新链表的头结点
2、pCur是要插入到新链表的节点。
3、定义一个pNex作为一个中转变量,临时保存的pCur的next,也就是下一个要插入新链表的节点信息。
4、将当前dummy的指向(dummy指向nil)赋值给当前要插入新链表中的节点(原来指向pNex,赋值后也指向nil)
5、调整dummy的指向,让指针指向当前要插入的节点pCur
经过4、5 新链表中就形成了一个 dummy->pCur->nil的链表
6、需要循环原链表 ,则要保持原链表中pCur != nil ,所以,要将3中的pNex赋值给pCur继续进行循环(即重复3~6步),直到pCur没有值了方可罢休
此时,上代码
func reverse(head *ListNode) *ListNode {
//简称,头插法
newList := new(ListNode) //步骤1
pCur := head //步骤2
for pCur != nil {
pNex := pCur.Next //步骤3
pCur.Next = newList.Next //步骤4
newList.Next = pCur //步骤5
pCur = pNex //步骤6
}
return newList.Next //循环完毕,返回原链表的翻转链表
}
方法二 :就地翻转
直接上图解释
1、dummy是头结点,指向首元节点prev
2、pCur是待翻转的节点
3、将pCur的指向赋值给prev(这样做,就可以吧prev到pCur的指向断开)
4、将dummy的指向赋值给pCur(这样做,就可以把pCur指向下一个节点3的路断开,并让pCur重新指向prev)
经过3、4 就可以把prev,pCur进行位置翻转
5、此时,再把dummy的指针指向pCur,就可以形成了:头->2->1 ....的链表
6、需要循环原链表 ,则要保持原链表中pCur != nil ,所以,需要pCur = prev.Next (即重复3~6步),直到pCur没有值了方可罢休
代码就不上了,大同小异
最后,上个打印的方法,因为存储直接打印就是地址了,需要把值展示出来才直观
func printNode(head *ListNode) {
for head != nil {
fmt.Println(head.Val)
head = head.Next
}
}
有疑问加站长微信联系(非本文作者)