Write a Program to reverse a Linked list

There are many ways to reverse a linked list, but here we’ll discuss 2 methods to do so.

1.  Iterative Method:

This is the most simple method to reverse a linked list. This is the first thought that would come to anybody’s mind if he/she thinks on how to reverse a linked list. Let’s take a simple linked list:

reverse a linked list

 

Now what we are gonna do is to make the last node as head and first as tail, so simply we will reverse the links in opposite direction and make head as last member of linked list, so that the linked list becomes reverse.

Technically: Iterate through the linked list. In loop, change next to prev, prev to current and current to next.

Now let’s implement this in program:

Reverse a Linked List using Iterative method:

Sample Output:

Time Complexity: O(n)
Space Complexity: O(1)

 

2.  Using Recursion:

  • Divide the list in two parts – first node and rest of the linked list.
  • Call reverse for the rest of the linked list.
  • Link rest to first.
  • Fix head pointer

reverse a linked list

 

Reverse a linked list using recursion:

Time Complexity: O(n)
Space Complexity: O(1)

Just use this function in the same program and you will get the output.

For any query comment below.

Be the first to comment

Leave a Reply