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

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

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

本文描述的是方法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个指针。
逻辑分析图:
在这里插入图片描述

本来我想用wps来设计图片,发现wps放大缩小比较困难,本文需要的图片又比较多。processon架构图设计工具是3年前滴滴的一个副总裁推荐给我的,免费,挺好用:
在这里插入图片描述