206. 反转链表

题目：Leetcode 206.反转链表 （简单） （二刷）

解题思路：

该题目有多种解法：

① 每次生成新结点，尾插法

② 采用队列，先进先出，尾插法

③ 采用三指针，局部翻转链表

④ 递归

代码

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        # 三指针实现局部翻转链表
        if head == None or head.next == None:
            return head
        sentry = None
        cur = head.next
        pre = head
        pre.next = sentry
        while cur:
            temp = cur.next
            cur.next = pre
            pre = cur
            cur = temp
        return pre

时间复杂度O(n),空间复杂度O(1)

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        # 栈
        from collections import deque
        if head == None or head.next == None:
            return head
        deq = deque()
        while head:
            deq.append(head)
            head = head.next
        sentry = None
        while deq:
            cur = deq.popleft()
            cur.next = sentry
            sentry = cur
        return cur

时间复杂度O(n),空间复杂度O(n)

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        # 每次生成新结点
        if head == None or head.next == None:
            return head
        sentry = None
        while head:
            temp = ListNode(head.val)
            temp.next = sentry
            sentry = temp
            head = head.next
        return temp

时间复杂度O(n),空间复杂度O(n)

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        # 递归
        if head == None or head.next == None:
            return head
        last = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return last

时间复杂度O(n),空间复杂度O(n)

主要说一下递归，虽然消耗内存，同时比较难以理解，但是还是能锻炼思维的。

向下寻找到最后一个非空的结点，然后向上返回的过程中实现翻转，注意翻转完毕要制定head.next为空，
不然就会造成死循环

结论：我们可以看到三指针实现的局部反转的空间复杂度是O(1),是比较优的。但是不太好想到。