题目描述
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
image.png
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
解法一
迭代法，通过双指针标记前后继节点
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
# 迭代方法
# 定义前继，后继指针
pre, cur = None, head
while cur:
# 完成前后的next变换。Python 语言特性可以省略中间变量
cur.next, pre, cur = pre, cur, cur.next
return pre
解法二
递归。将问题拆分成当前节点与剩余的节点，只需要将剩余节点的第一个节点指向当前节点即可
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
# 1 -> 2 -> 3 -> 4 -> 5
# __________________
# 1 <- | 2 -> 3 -> 4 -> 5 |
# ------------------
# _____________
# 1 <- 2 <- | 3 -> 4 -> 5 |
# -------------
# 如果输入为空列表，则直接返回
if not head: return head
# 如果输入为最后一个节点，则返回当前节点，开始弹栈
if not head.next: return head
# 递归
newHead = self.reverseList(head.next)
# 设置第一个节点的next为当前节点
head.next.next = head
# 将当前节点的next置空。如果不设置，则对于最后一次弹栈，原链表头结点会指向第二个节点，导致无限循环
head.next = None
# 返回新链表的头结点
return newHead
