## Problem

Example:

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


• 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:

pre = ListNode(None)

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

for num in nums[1:]:
cur.next = ListNode(num)
cur = cur.next

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.