Skip to main content

Reverse a Linked List | Java | MyCodingNetwork

How to Reverse a Linked List

Hey everyone, welcome to another article on Linked List. Till now we have covered various operations on linked list and in this article, we would be unraveling another operation on Linked List to understand this data structure in a much deeper way. The problem statement of this article is: How to Reverse a Linked List.
Algorithm for reversing a Linked List iteratively:

There can be a several approaches to solve this problem, but in this article we would be restricting ourselves to iterative approach.

1. Create three nodes, ‘prev’, ‘curr’ and ‘next’.

      2.       Assign:

·         ‘prev’ as ‘NULL’

·         ‘curr’ as ‘head’

·         ‘next’ as ‘NULL’

      3.       Create a while loop with condition curr not equal to null. In each iteration:

·         ‘next’ is assigned with curr.next

·         ‘curr’ is made to point towards ‘prev’

·         Assign ‘prev’ with ‘curr’

·         Assign ‘curr’ with ‘next’

      4.       After the while loop terminates the previous node, contains the head of the linked list.

       Let's Implement this in the form of code:

Source Code:

reverse( ) function



In the above code, the reverse() function received head of the linked list as the parameter. First of all, inside the function base case is checked, if head is equal to null or head is pointing towards null then the functions should return. If the base case is not true, 3 pointers are allotted with the values null, head and null. The three pointers are 'previous', 'current', and 'next' (see the above code). After this, while loop starts which terminates when current is equal to null. Inside the while loop, firstly, 'next' is assigned with the node which is next to 'current'. Secondly, 'current' is made to point towards previous. Thirdly, 'previous' is assigned with the node 'current'. Lastly, 'current' is assigned with next 'node'.

After the while loop terminates, the function returns 'previous' node.

Output:



Working:

Here is the handwritten explanation of the above reversing algorithm:


Hope you liked this explanation, for any doubt/feedback/improvements/corrections you can comment down in the comment section.

Labels:

Popular posts from this blog

Pattern 2 | Java

  Problem Statement: Write a program to draw the following pattern: * * * * * * * * * * * * * * * (take a variable n which decides the number of rows, for above example, n=5) THE CODE Output: *  * *  * * *  * * * *  * * * * *  * * * * * *          * * * * * * *        * * * * * * * *      * * * * * * * * *    * * * * * * * * * * Simplification : In the above problem, the value of n is 10 (i.e., the number of rows are 10) 1. In the first for loop we have i as the counter variable with initial value of 1 and having a condition i.e. i should be less than or equal to n.  It has a print statement after the second for loop,  System.out.println(); w hich is used for changing the row, each time for the second for loop terminates. 2. In the second for loop we have j as the counter variable with initial value of 1 having a condition i.e. j  should be  less than or equal to i (the value of i  will be as per the current ongoing iteration). Further it has an updation statement j++  Inside the seco
Discover More »

Code #1 | Hello Java | Basics of Java

Today starting with a very basic coding program in Java. So, the program is Write a program in Java to print "Hello Java!" Output: Hello Java!
Discover More »

Bubble Sort | Java & Python | MyCodingNetwork | Alok Tripathi

  Bubble Sort is a simple sorting algorithm that works by repeatedly comparing and swapping adjacent elements in an array until they are in the correct order. It is called bubble sort because the smaller elements "bubble" to the top of the array, while the larger elements sink to the bottom. Quick Video Explanation: How Bubble Sort Works Bubble sort works by iterating through the array from left to right and comparing each pair of adjacent elements. If the element on the left is larger than the element on the right, they are swapped. This way, the largest element in the array moves to the rightmost position in each iteration. This process is repeated until no more swaps are needed, which means the array is sorted. To illustrate how bubble sort works, let's use the example of sorting the array [30,90,50,10,40] in ascending order. First Iteration/Pass: The first step is to compare the first two elements, 30 and 90. Since 30 is smaller than 90, they are already i
Discover More »