## Problem

Reverse a singly linked list.

Example:

```
Input: 1->2->3->4->5->NULL
Output: NULL<-1<-2<-3<-4<-5
```

Follow up:

- A linked list can be reversed either iteratively or recursively. Could you implement both?

## Thought Process

if to reverse a link list iteratively, need three pointers to store

- pre => previous node
- cur => current node
- nxt => next node (here nxt is different from node’s own next reference)

Iterate thru ll, for any given state:

- cur.next => pre
- pre => cur
- cur => nxt
- nxt => nxt.next

## White Board

Below is the white board:

## Code

```
# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def reverseList(self, head):
pre = ListNode(None)
cur = head
while cur is not None: #O(n)
# store the current next node
nxt = cur.next
cur.next = pre
# reverse the node
pre = cur
cur = nxt
nxt = cur.next
# now cur is None, pre is the last node from the original ll
# pre is the head node for the new ll
return pre
def create_ll(nums):
if len(nums) == 0:
return None
head = ListNode(nums[0])
cur = head
for num in nums[1:]:
cur.next = ListNode(num)
cur = cur.next
return head
def test_ll():
nums = list(range(5))
curr = create_ll(nums)
while curr is not None:
print(curr.val, end="=>")
curr = curr.next
print("None")
test_ll()
```

```
0=>1=>2=>3=>4=>None
```

## Complexity

- Time complexity is O(n)

## Optimization

Will try to figure out a recursive solution in the future.