glang--单链表翻

20190729 · · 489 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

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)
}

然后,开始介绍我所理解的方法

方法一:新建一个链表(只有头结点),然后遍历需要翻转的链表,逐个插入到新链表中即可,最后新链表就是原链表的翻转链表,如图

image.png

image.png

图例解释:
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  //循环完毕,返回原链表的翻转链表
}

方法二 :就地翻转

image.png
image.png

直接上图解释

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
    }
}

有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:20190729

查看原文:glang--单链表翻

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

489 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传