How to Reverse a Linked List

A common algorithm question is “How to Reverse a Linked List”. Below the SimpleLinkedList (Java) class contains a simple example to follow.

The class SimpleLinkedList contains one field, head, which is used to keep track of the head (first) node of the linked list.

The nested class Node is the class used to create nodes (items) contained in the linked list. Each node contains a reference to the next node in the list, stored in the next variable.

The main method illustrates how to add items to a SimpleLinkedList object, as well as call the reverse method on that object.

The reverse method works by using a loop to visit each node in the linked list. For each iteration of the loop, the curr, prev, and next local variables are used take a node’s next, and make it the node’s previous. For example, the first node has no previous node. The first node’s previous will become the original second node, while the first node’s next will become null (making it the last node). The head node of the newly reversed linked list is returned to make it possible to assign this as the new head of the SimpleLinkedList object.

The full example is shown below as well as on the Big Datums GitHub repo.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">