反转链表
题目
题意：反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL思路
再定义一个新的链表，实现链表元素的反转，但是会造成内存空间的浪费。
另外一种方法是使用迭代的方式，将链表的指针方向进行反转。具体如下：
首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null。
然后就要开始反转了，首先要把 cur->next 节点用tmp指针保存一下，也就是保存一下这个节点。
为什么要保存一下这个节点呢，因为接下来要改变 cur->next 的指向了，将cur->next 指向pre ，此时已经反转了第一个节点了。
接下来，就是循环走如下代码逻辑了，继续移动pre和cur指针。
最后，cur 指针已经指向了null，循环结束，链表也反转完毕了。 此时我们return pre指针就可以了，pre指针就指向了新的头结点。
其他解法：
- 使用虚拟头结点
- 使用栈
解法
使用迭代的方法：
func reverseList(head *ListNode) *ListNode {
var pre *ListNode
cur := head
for cur != nil {
tmp := cur.Next
cur.Next = pre
pre = cur
cur = tmp
}
return pre
}使用递归的方法：
func reverseList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
p := reverseList(head.Next)
head.Next.Next = head
head.Next = nil
return p
}使用虚拟头结点的方法：
func reverseList(head *ListNode) *ListNode {
dummy := &ListNode{}
for head != nil {
next := head.Next
head.Next = dummy.Next
dummy.Next = head
head = next
}
return dummy.Next
}使用栈的方法：
func reverseList(head *ListNode) *ListNode {
stack := make([]*ListNode, 0)
for head != nil {
stack = append(stack, head)
head = head.Next
}
dummy := &ListNode{}
cur := dummy
for len(stack) > 0 {
cur.Next = stack[len(stack)-1]
cur = cur.Next
stack = stack[:len(stack)-1]
}
cur.Next = nil
return dummy.Next
}