206.反转链表

题目

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例一

1 2	输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]

示例二

1 2	输入：head = [1,2] 输出：[2,1]

示例三

1 2	输入：head = [] 输出：[]

思路

方法一：迭代+三指针

需要三个指针(有些题解叫双指针，但我感觉三指针更准确些)pre、cur、nex分别指向前一个节点、当前节点和下一个节点。

pre初始值None，cur初始指着头节点、nex初始则是头节点的下一个节点。

每次操作如下：

cur将下一个节点指向pre，实现局部的链表反转
pre和cur往后移动一个节点
nex是一个临时存储节点的变量。第一步cur将下一个节点指向pre时会失去移动的方向，这个时候就直接用nex来帮助cur移动

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        pre = None
        cur = head
        while cur != None:
            nex = cur.next
            cur.next = pre
            pre = cur
            cur = nex
        return pre

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

评论区大佬的超级精简版

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

class Solution:
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        p, rev = head, None
        while p:
            rev, rev.next, p = p, rev, p.next
        return rev

方法二：递归

做了几题发现，链表使用递归是比较常见的作法。

有几个问题(我遇到的)需要注意：

递归反转如何避免成环。
新的头节点怎么找到。

考虑上述问题后的步骤：

递归到最后一个节点，将该节点设置为新的头节点，并作为函数的返回值
在回溯的过程中，将当前节点的下一个节点的next指针指向当前节点实现反转

为了避免成环，将当前节点的下一个节点(此时还指向原来的下一个节点)指向None/null(缺少这一步，在回溯过程结束时会导致原链表的头节点区域成环，比如应该是1<-2<-3<-4<-5，结果是1<->2<-3<-4<-5，这样程序就困在环里直到超时)

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head==None or head.next==None:
            return head
        newhead = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return newhead