How

• Iteratively

从head开始，挨个反转，需要prev, curr追踪上一个节点和现在的节点，由于中间的连接要断开，所以先把nxt记录下来再反转，然后移动到下一个需要反转的节点。遍历到最后curr为空也就是prev是最后一个节点，将prev作为反转后的head返回。

• Recursively

base case就是此时的sublist只剩一个节点也就是到了链表的尾部，此时直接返回。

如果考虑中间状态，已经反转好的部分（上层迭代的返回值）设置为newHead，然后反本层迭代的节点即node，最后将node指向新的尾部None。完成后返回新的头节点newHead

Code

Iteratively

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev, curr = None, head
        # T O(n) M O(1)
        while curr:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt
        return prev

Recursively

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # Base case: if the head is None or the list has only one node
        if not head or not head.next:
            return head
        
        # Recursively reverse the sublist starting from head.next
        newHead = self.reverseList(head.next)
        
        # Reverse the pointers
        head.next.next = head
        head.next = None
        
        return newHead

Complexity

Iteratively

Time $O(n)$

Space $O(1)$

Recursively

Time $O(n)$