题解 | #反转链表#

方法一：构造链表（我采用的方法，不是最优解）

解题思路

1. 循环，让指针p指向链表的尾节点，同时用字典存储每个链表的前驱节点，用于重构链表
2. 根据字典重新构建反向的链表

代码：

    def ReverseList(self , head: ListNode) -> ListNode:
        # write code here
        # 特例处理
        if not head: return None
        # 让指针指向尾节点，并存储每个节点的后继节点
        dic = {}
        dic[head] = None
        p = head
        while p.next:
            dic[p.next] = p
            p = p.next
        print(dic)
        revhead = p # 反转后的头节点
        while p:
            p.next = dic[p]
            p = dic[p]
        return revhead

• 时间复杂度O(n + n)，需要遍历两次链表
• 空间复杂度O(n)，需要一个字典存储链表

方法二：三指针法

当要求空间复杂度为1时采用这种方法

解题思路：

1. 初始化三个指针，
	- pre指针指向已经反转好的链表的最后一个节点，最开始没有反转指向null
	- cur指针指向待反转链表的第一个指针，最开始第一个节点待反转，指向head
	- nex指向待反转链表的第二个节点，目的是保存链表，当cur改变指向后，后面的链表就都失效了，所以需要保存
2. 循环执行
	- nex=cur.next
	- cur.next = pre
	- pre = cur
	- cur = nex

代码：

    def ReverseList(self, head: ListNode) -> ListNode:
        # write code here
        if not head: return None

        pre, cur, nex = None, head, head.next

        while cur:
            nex = cur.next
            cur.next = pre
            pre = cur
            cur = nex
        return pre

• 时间复杂度O(n)，只需要遍历链表一次
• 空间复杂度O(1)，无需额外的存储空间