翻转链表

问题

对于一个这样的链表：

希望经过函数处理后，变成这样：

链表结构定义

节点的定义为：

type Node struct {
	Value int
	Next  *Node
}

构造链表方法为：

func createLinkedList(n int) *Node {
	head := &Node{Value: 0}
	node := head
	for i := 0; i < n; i++ {
		if i < n {
			node.Next = &Node{Value: i + 1}
		}
		node = node.Next
	}
	return head
}

函数会返回一个链表的指针。使用指针而不是结构体类型是因为，Go 语言的某些关于变量的设计，无法使用 Node{} == nil 的形式判断变量是否为空，因为理论上 Node{} 不是 nil。这就造成了如果使用Node{}作为链表头部的变量类型，在遍历的时候找不到一个合理的结束时机，只能使用类似 Node{}.Next == nil 这样的形式，还会遗漏掉最后一个节点。

迭代翻转链表

这里不能使用直接改变节点值的方式，比如遍历一次后把链表节点的值按照顺序储存到数组中，然后再遍历一次，一次修改链表节点的值。这个违背了数据结构的意义。可以使用递归完成翻转链表的操作。

比如第一个节点，使用 temp 变量储存翻转前的下一个节点的位置，然后把 head.Next 指向翻转后应该有的节点位置，第一个节点的下一个节点是空节点，第二个节点的下一个节点是节点 1。完成 head.Next 的指向后，head 要指向 temp 也就是原来的下一个节点用以完成遍历。这时还需要要用一个 curr 变量来储存head 跳转前的位置，方便下一次 head.Next 指向上一个节点的位置。这应该是一个简单的过程。

func reverseLinkedList(head *Node) *Node {
	curr := new(Node)
	for head != nil {
		temp := head.Next
		head.Next = curr
		curr = head
		head = temp
	}
	return curr
}

• 时间复杂度：O(n)
• 空间复杂度：O(1)

执行

执行程序后结果和预期一致：

func main() {
	head := createLinkedList(4)
	head = reverseLinkedList(head)
	for head != nil {
		fmt.Println(head.Value)
		head = head.Next
	}
}