翻转链表

问题

对于一个这样的链表:

50

希望经过函数处理后,变成这样:

50

链表结构定义

节点的定义为:

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 这样的形式,还会遗漏掉最后一个节点。

迭代翻转链表

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

50

比如第一个节点,使用 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
	}
}