# Reverse Linked List

## # 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
curr = head
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:
prev, curr = None, head
while curr:
curr.next, prev, curr = prev, curr, curr.next
return prev
```

### # Recursion (REDO)

There are `n`

nodes in total. Assume `curr`

node is

Set `next`

to `.next.next`

=

Also avoid the cycle by setting `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:
curr = head
# not curr covers the empty input: []
if not curr or not curr.next:
return curr
hd = self.reverseList(curr.next)
curr.next.next = curr
curr.next = None
return hd
```