## # Definition for singly-linked list

class ListNode:
def __init__(self, x):
self.val = x
self.next = None


## # Solution

This problem is very basic yet IMPT. It can be solved both iteratively or recursively.

### # Iteration

It's quite IMPT to understand and remember the steps in while loop.

Complexity:

• time:
• space:
def reverseList(self, head: ListNode) -> ListNode:
prev = None
while curr:
# store next node
nxt = curr.next
# update next of current
curr.next = prev
# move prev and curr 1 step forward
prev = curr
curr = nxt

return prev


or could combine the assignments (Python's syntactic sugar):

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


### # Recursion (REDO)

There are n nodes in total. Assume to have been reversed and the curr node is :

Set 's next to : .next.next =

Also avoid the cycle by setting 's next to None: .next = None

Note that I set head to curr to avoid confusion. hd is the actual head of reversed linked list.

Complexity:

• time:
• space: due to implicit stack space
def reverseList(self, head: ListNode) -> ListNode: