链表 之 反转链表

示例:

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

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

方法1：三指针法

设指针cur指向当前节点，反转指针的过程是改变当前节点的next指针指向当前节点前一个结点，所以同时需要保存前一个节点和下一个节点，设指针pre指向当前节点前一个节点，指针next指向当前节点下一个节点。cur指针最初指向链表首节点，next指向cur下一个节点，pre为空，改变当前节点的next结点指向pre指向的结点，每这样操作一次，三个指针同时前进，直到链表尾部为止。最后，返回反转后的链表表头指针。

时间复杂度：O(n)

空间复杂度：O(1)

class Solution:

    def reverseList(self, head: ListNode) -> ListNode:

        pre = None

        cur = head

        nex = None

        while cur:

            nex = cur.next

            cur.next = pre

            pre = cur

            cur = nex

        return pre