前往此题

解题思路

迭代法
思路其实很简单就是把链表指向全都倒过来,我们将通过双指针来辅助实现。
把 1->2->3->4->5 变成 1<-2<-3<-4<-5。
千万不要理解成把它变成 5->4->3->2->1
prev、tmp做辅助

cur(当前)指向prev(前一个)
prev(前一个)变成cur(当前)
cur(当前)变成下一个
重复上面步骤

代码实现

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

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev = None
        curr = head
        while curr:
            temp = curr.next
            curr.next = prev
            prev = curr
            curr = temp
        return prev

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)

递归
思路其实和迭代一样，先递归到底然后再一步一步往前改变指向。
这里最难理解的地方就在于如何去改变指向。
比方说有这么一个链表：
1->2->3->4->5->null
我们想把5的指向从null改为4。这个时候需要在递归到4的时候，将4.next.next = 4 也就是 4.next=5.next=4。这样想应该很好理解，打个比方说我徒弟是张三，也就是说我是张三的师傅。现在变成我徒弟的徒弟是我，我的徒弟是张三，张三的徒弟是我，就变成了张三是我的师傅了。

理解了这一步其他就很简单了

终止条件：
head 为空或者 head.next为空

if not head or not head.next: return head

代码

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

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next: return head

        cur = self.reverseList(head.next)
        head.next.next = head
        head.next = None

        return cur

复杂度分析

• 时间复杂度 O(N)
• 空间复杂度 O(1)