Reverse Linked List — Leetcode (Recursion)

We have been given a classic problem to solve the Reverse Linked List Problem.
I will be solving this solution using the concept of recursion.
I have prepared a section at the end of this article which defines what all is necessary to know before leaping in with the solution of this problem.
#recursion #linkedlist #leetcodesolution

Question : Given the head of a singly linked list, reverse the list, and return the reversed list.

Example 1:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Example 2:

Input: head = [1,2]
Output: [2,1]

Example 3:

Input: head = []
Output: []

Constraints:

• The number of nodes in the list is the range [0, 5000].
• -5000 <= Node.val <= 5000

Approach :

So Let’s talk about the proper apporach we will be using to solve this question.

We will be considering the base case as when head is null or when head’s next is null.
Then we will be stroring the next node(second node in the linkedlist) in a new variable and setting the value of head’s next to null.
After doing this we will simply call the recusrive function through a new ListNode variable left(nodes which are left) which would be used to call the reverseString and pass the next node(second node as the head). At the end our function would simply return left(left nodes).

I hope the approach was clear and it is understood.

Solution in Java Language :

The time complexity of this solution is : O(n)
It is not the only approach we have for this particular solution.

A few things you should know before moving on with the solution to understand the concept better :

1. What are Linked List in Java ?
   → Linked List are designed to give better performance when you insert or delete elements from the middle of the collection.
   Linked List is a data structure which is used for storing collections of data. A linked list has the
   following properties:
   ● Successive elements are connected by pointers.
   ● Can grow or shrink in size during the execution of a program.
   ● Can be made just as long as required (until systems memory exhausts).
   ● Does not waste memory space (but takes some extra memory for pointers). It
   allocates memory as the list grows.
2. What is Recursion?
   → Recursion is one of the most important topic in programming whether you want to go for Competitive Programming or you just want to crack Company Interviews you will always be in need of this concept.
   So an easy explanation of Recursion is :
   Recursion is a process in which a function calls itself.
   now that won’t be an answer your interviewer is hoping from you.
   A more professional defination of Recursion is,
   Recursion is a concept in computer programming in which the answer of the problem relies on the subproblem of the question also, the process is repeated until a desired condition is met(base case).