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

Exploring Uninformed Search in Artificial Intelligence: Basics and Applications

  In artificial intelligence (AI), search algorithms are essential for solving a variety of problems, from navigating a maze to scheduling tasks. Uninformed search, also known as blind search, is a fundamental category of search techniques where the algorithm has no additional information about the states beyond what is provided in the problem definition to guide the search. This page delves into the basics of uninformed search algorithms, their types, and their applications in AI. Understanding Uninformed Search Uninformed search algorithms explore the search space without any guidance on which paths might lead to the goal more efficiently. They rely solely on the information available from the initial problem setup, such as the start state, goal state, and possible actions. This approach contrasts with informed search algorithms, which utilize heuristics to make more educated guesses about the best path to take. Types of Uninformed Search Algorithms   Several uninformed se...
Discover More »

Artificial Intelligence Playlist

Here's a playlist specifically dedicated to Artificial Intelligence. Make sure to follow it, as a whole lot of new AI videos coming up... 1. Concept of State in AI 2. Uninformed Search in AI 3. Breadth First Search | Part 1 4. Breadth First Seach | Part 2 | Algorithm & Working and many more to come...
Discover More »

Print a Linked List in Reverse Order | Linked List | Java | MyCodingNetwork

  Print a Linked List in Reverse Order After mastering the four standard operations on a Linked List - Creation, Traversal, Insertion, and Deletion - we will now proceed to the next topic: ' Printing a Linked List in Reverse Order '. It serves as a continuation of our previous discussions. We will build upon the topics and ideas that we have previously explored to further our understanding about Linked List. We 'll be using recursive approach for the implementation. For this a separate recursive function would be needed. Concept of stack is also implemented for print statement. Let's discuss the algorithm for the same: Algorithm: Create a function printReverse() , which takes 'head ' of the Linked List as the parameter. Take a temporary node ' cur ' and assign it with the head of the list. Create a base case which checks if cur==null . If base case is TRUE, then function would return . If base case is FALSE, then the statements following that base case ...
Discover More »