golang反转单链表-木庄网络博客

本文摘自php中文网，作者TangYiMo，侵删。

双链表不需要反转，只需要在引用时改变头的引用位置即可。单链表反转，有2种做法：

1重构方法，将node存储在有序容器中，例如切片中，然后重新构建一条链表。
2直接反转指针法，保存好Node前后索引，改变指针的指向。

一般我经常用linux kernel的双链表，插入，查找，删除正向反向索引，都贼灵活，几乎不用单链表。在生产环境哪个程序员如果用单链表，可以怼死他先，用单链表的程序员这不是sb吗。不过面试有的公司会问，这时候问你什么你就答什么就好，因为这个人虽然技术可能不如你或者比你差很多，但是他是面试时你与那家公司沟通的唯一渠道（一般的公司面试都是单人面试。遇到格局比较大的是以公司选人才为准，遇到格局不大的任何一个方面你让人不爽，就没戏了。这个其实是人性了。例如当官的，任何部门的一把手都是一个人说了算的，出问题时，情况与此完全一致）。

本文描述的是方法2。 源码：

root@jack-VirtualBox:~/test/list# cat main.go 
package main

import "fmt"

type List struct {
    next *List
    val  int
}

func main() {
    fmt.Println("vim-go")

    var head *List
    var prev *List

    // 构建链表
    for i := 0; i < 8; i++ {
        i := i
        node := &List{val: i}
        if head == nil {
            head = node
            prev = node
            continue
        }

        prev.next = node
        prev = node
    }

    pl := func(head *List) {
        for head != nil {
            fmt.Println(head.val)
            head = head.next
        }
        fmt.Println()
    }

    // 打印链表
    pl(head)

    // 取反链表
    reserverlist := func(head *List) *List {
        if head == nil {
            return nil
        }

        //var ptmp *List
        next := head.next
        head.next = nil

        for next != nil {
            ptmp := next.next
            next.next = head

            head = next
            next = ptmp
        }
        return head
    }

    head = reserverlist(head)
    pl(head)
    head = reserverlist(head)
    pl(head)
    head = reserverlist(head)
    pl(head)
    head = reserverlist(head)
    pl(head)
}
root@jack-VirtualBox:~/test/list#

执行：

root@jack-VirtualBox:~/test/list# go run main.go 
vim-go
0
1
2
3
4
5
6
7

7
6
5
4
3
2
1
0

0
1
2
3
4
5
6
7

7
6
5
4
3
2
1
0

0
1
2
3
4
5
6
7

root@jack-VirtualBox:~/test/list#

以3个节点为例，需要反转中间的2个指针。逻辑分析图：在这里插入图片描述