# Reverse LinkedList — Day 6(Python) Photo by Hush Naidoo on Unsplash

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->NULLOutput: 5->4->3->2->1->NULL`

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.

1. Holds the previous node.
2. Holds the current node.
3. Holds the next node.

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

1. Initialise previous(A) pointer to “None”.
2. Let current pointer(B) point to head of the linked list.
3. Run the loop until current reach the end.
4. Next pointer(C) points to next of current.
5. Next of current pointer points to previous. B -> A
6. Previous pointer is now current node.
7. 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.

1. 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.
2. If we have to run through few nodes before reaching the base condition, recursively call the function.
3. The next to the next of head is head and next of head is None.
4. 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.

--

--