【题目链接】

题解

1. 动画演示+多种解法 206. 反转链表
2. 反转链表

思路

代码

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

class Solution:
    ### 0102 迭代（36 ms，15.4 MB）
    def reverseList(self, head: ListNode) -> ListNode:
        # 初始化两个辅助节点
        pre, cur = None, head

        # 使用迭代进行循环
        while cur:
            node = cur.next
            cur.next, pre = pre, cur
            cur = node
        
        return pre # 返回最后一个节点，即新的头节点

    ### 0102 递归（48 ms，19.5 MB）
    def reverseList(self, head: ListNode) -> ListNode:
        # 递归终止条件
        if not head or not head.next: return head

        # 开始递归，cur表示最后一个节点
        cur = self.reverseList(head.next)

        # 节点指向反向操作
        # head表示当前节点，head.next表示当前节点的下一节点
        # head.next.next表示下一节点的指向，将其重新指向为当前节点，即指向反向操作
        head.next.next = head

        # 为防止循环，需要将当前节点head的指向置为空None
        head.next = None

        return cur # 返回最后一个节点