Day.8 Reverse Linked List

Leetcode #206. Reverse Linked List

简单来说这一题要做反转链结
ex.
input: 1->2->3->4
output: 4->3->2->1

如果你没做过这题，强烈建议你先思考一下怎麽解。

防雷
防雷
防雷

最直觉的方式可以新建一个slice([]*ListNode)，去把全部的节点都放进去，最後slice从尾去读取，重新建一个链结就行了。

这样做的时间复杂度为O(n)，空间复杂性O(n)要用slice存下链结的地址。

现在为大家介绍一个更好的解法，可以省下一些记忆体。

先来看一下它的流程:

1 2 3 4
2 1 3 4
3 2 1 4
4 3 2 1

每一次新节点都把第一个节点接在後面，当你跑完本个链结，就完成反转了。

来看一下程序:

func reverseLinkedList(head *ListNode) *ListNode {
	// prevNode一开始为是空
	// 这样第一个节点的next会接到nil，才不会造成无限的链结
	var prevNode *ListNode
	currentNode := head

	// 节点交换的过程
	for currentNode != nil {
		temp := currentNode.Next
		currentNode.Next = prevNode // 最前面的节点接到目前节点的後面
		prevNode = currentNode
		currentNode = temp
	}

	return prevNode // 回传第一个节点
}

明天来解其他题目～