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

YouTube Material 1| Hindi Video

Video Lecture- https://youtu.be/StCjnwfS0NQ Basic structure of a Java program public class xyz { public static void main(String args[]) { //Code //Code //Code //Code //Code }} public - access specifier/modifiers which makes the particular entity accessible throughout the program i.e., it can be accessed by other classes also. static - a keyword by which we don't have to create an object of that particular entity. void- return type keyword by which the function becomes non-returning type. main - name of the function String args[] - argument for main function Print Statement Syntax: System.out.println() ; Three types of Iteration statements are: for loop Example: for(int i=0; i<=5;i++) { //Code //Code //Code //Code //Code } The body of the above for loop will be executed 6 times. while loop( entry control loop) Syntax: while (condition) { //Code //Code //Code //Code //Code } The body of the above while loop will be executed continuously as long as the condition of the while is tr...
Discover More »

Pattern 1 | Java

Problem Statement: Write a program to draw the following pattern of NxN(where N is the input): * * * * * * * * * * * * * * * * * * * * * * * * * (here, N=5) THE CODE Output: Here, the input is 8 Simplification : In the above problem, two for loops are used: 1. The first for loop is having i as counter variable with  initial value of 1 and ending value of 10 with an updation statement i++. 2. The second for loop is having j as counter variable with initial value of 1 and ending value of 10 with an updation statement j++. The second  for loop is used to print  * in the respective column (the value of j represents the column number). It is having a print statement System.out.println("* ") to print * in each column(for convenience, I've added a space for better visibility of columns in the output). The first for loop is used to define rows( the value of i represents the row number). It is having a print statement System.out.print() to change rows each time the second for ...
Discover More »

Binary Search | The-Algorithm-Drive | MyCodingNetwork

Binary Search The next algorithm, we are going to study is Binary Search . As the name suggests, it is a searching algorithm. It is one of the very famous searching techniques. Unlike its counterpart linear search, it is way more advanced.  Time complexity of linear search is O(N) whereas that of binary search is O (log N). Source Code: Output Number Found at index =5 Working Let’s come on to the working of the algorithm, as you can see in the above program, we need a sorted array to perform binary search algorithm. 1.    Here, bin function in the above program it accepts 4 parameters, that is, the array arr , lower index low , higher index high and the searching number sn . 2.    Next, we have a do-while loop to check if high is greater than or equal to low (high>=low). If at any point of iteration this condition is not satisfied, it means the searching number sn does not exist in the array. Following is the algorithm for binary search: while ...
Discover More »