# Reverse LinkedList — Day 6(Python)

Today we will learn how to reverse a linked list. The basic features of the linked list are covered in Day 2 of the 365dayschallenge series. You can follow this link if you require a refresher.

**206****. Reverse Linked List**

Reverse a singly linked list.

**Example:**

**Input:** 1->2->3->4->5->NULL

**Output:** 5->4->3->2->1->NULL

**Follow up:**

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

Before we jump into the solution, let us run into a few more examples.

Input:1->NULLOutput:1->NULLInput:1->2->NULLOutput:2->1->NULLInput:NULLOutput:NULL

Solution — Iterative Approach

To reverse a linked list through iterative approach we would require 3 pointers.

- Holds the previous node.
- Holds the current node.
- Holds the next node.

We just need to learn how to manipulate above three pointers in order to reverse a linked list.

- Initialise previous(A) pointer to “None”.
- Let current pointer(B) point to head of the linked list.
- Run the loop until current reach the end.
- Next pointer(C) points to next of current.
- Next of current pointer points to previous. B -> A
- Previous pointer is now current node.
- Current pointer is now Next of current

`class Solution:`

def reverseList(self, head: ListNode) -> ListNode:

if head == None or head.next == None:

return head

prev, curr = None, head

while curr:

next_node = curr.next

curr.next = prev

prev = curr

curr = next_node

return prev

Complexity analysis

**Time Complexity**

We would be required to traverse through each of the element in LinkedList and that would take O(N) time.

**Space Complexity**

We are not using any extra data structure to store in the above logic. Hence space complexity is O(1).

Solution — Recursive Approach

When using recursive approach, we need a base condition.

- For this question our base condition is when head is either None or next of head is None. We need to return head when we reach base condition.
- If we have to run through few nodes before reaching the base condition, recursively call the function.
- The next to the next of head is head and next of head is None.
- Then return Current.

`class Solution:`

def reverseList(self, head: ListNode) -> ListNode:

if head == None or head.next == None:

return head

curr = self.reverseList(head.next)

head.next.next = head

head.next = None

return curr

An animated version of above logic is given below.

**Time Complexity**

We would be required to traverse through each of the element in LinkedList and that would take O(N) time

**Space Complexity**

Internally recursive function uses a stack to execute the program. Hence space complexity is O(N).

I would like to improve my writing skills so any suggestions or critiques are highly welcomed.