反转链表
题目：206. 反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2]
输出：[2,1]
示例 3：
输入：head = []
输出：[]
提示：
- 链表中节点的数目范围是
[0, 5000] -5000 <= Node.val <= 5000
方法一：
创建一个新的空链表，然后扫描老链表节点，并将扫描到的结点使用头插法插入空链表，这样就得到了一个反转的链表。
func reverseList(head *ListNode) *ListNode {
var newListNode *ListNode
cur := head
for cur != nil {
newListNode = &ListNode{Val: cur.Val, Next: newListNode}
cur = cur.Next
}
return newListNode
}
一个for循环，时间复杂度O(n)，用了额外的链表长度空间，空间复杂度O(n)。
方法二：
能不能让时间复杂度降为O(1)呢？反转链表不就是反转指针嘛，只要让指针指对了就行了。具体请看：[代码随想录](代码随想录 (programmercarl.com))
具体步骤如图：
func reverseList(head *ListNode) *ListNode {
cur := head
var pre *ListNode
for cur != nil {
temp := cur.Next
cur.Next = pre
pre = cur
cur = temp
}
return pre
}
时间复杂度O(n)，空间复杂度O(1)。