反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

解法 1

在遍历列表时，将当前节点的 next 指针改为指向前一个元素。由于节点没有引用其上一个节点，因此必须事先存储其前一个元素。在更改引用之前，还需要另一个指针来存储下一个节点。最后返回新的头引用。（注：Python 中可直接交换变量）

def reverse_list(head):
    if not head or not head.next:
        return head
    pre, cur, = None, head
    while cur:
        cur.next, pre, cur = pre, cur, cur.next
    return pre

执行用时 :56 ms
内存消耗 :14.8 MB

时间复杂度：O(n)，n 是列表的长度。
空间复杂度：O(1)。

解法 2

递归解法是从链表结尾开始向链表头部逐个反转，将后一节点的 next 指针改为指向当前节点，并将当前节点的 next 指针改为 None。

def reverse_list(head):
    if not head or not head.next:
        return head
    next = reverse_list(head.next)
    head.next.next = head
    head.next = None
    return next

执行用时 :52 ms
内存消耗 :19.4 MB

时间复杂度：O(n)，n 是列表的长度。
空间复杂度：O(n)，由于使用递归，将会使用隐式栈空间。递归深度可能会达到 n 层。

参考

https://leetcode-cn.com/problems/reverse-linked-list/