206. 反转链表

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

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

---

双指针法

申请两个指针，pre 最初指向 null，cur 指向 head，然后遍历cur

每次迭代到 cur，都将 cur的 next指向 pre，然后 pr e和 cur 往后移一位, 注意保存 cur 的 next 节点，避免链表断开

迭代完成后 cur 变成 null，pre 就是最后一个节点。

备注

• 时间复杂度：O(n)

• 空间复杂度: O(1)

警告

依赖 python 的语法特性，链表节点的交换可以一行语句搞定，但不容易记忆

编写时脑海中可以模拟交换的过程，一个变量一个变量的写，达到最终效果如下

cur.next = pre

cur.next, cur = pre, cur.next

cur.next, cur, pre = pre, cur.next, cur

---

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        pre = None
        cur = head
        while cur:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp
        return pre