Analytics Vidhya
Published in

Analytics Vidhya

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->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->NULL
Output: 1->NULL
Input: 1->2->NULL
Output: 2->1->NULL
Input: NULL
Output: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.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store