Reverse a Linked List

Posted by Mark Henry on June 11th, 2021

What exactly is a linked list?

A linked list is a succession of data structures with pointers connecting the nodes and the last node pointing to NULL, according to the general definition.

A linked list is a collection of links that comprise elements that are linked together via pointers. A connection to another node is contained in each pointer link. After arrays, the linked list is the most often used data structure.

A linked list is made up of three parts:

Each node contains data, which is referred to as an element.

Every linked list node contains a link to the next link, which is Next.

A head pointer is a pointer in a Linked List that points to the first link.

What Is the Best Way to Reverse a Linked List?

Reversing the list entails reversing all of the items, which we can accomplish by reversing all of the connections and setting the next pointer to the prior node.

Reversing a Linked List in an Iterative Way

If the linked list contains only one or no elements, the current list is returned unchanged. If there are two or more items, we can use three-pointers to build an iterative solution.

We'll write a function that reverses the linked list, using the head node as the single parameter and returning the new linked list's head:

Step 1: Create three nodes, one having a reference to the head node and named current, and the other two with NULL pointers named temp and prior.

Step 2: We'll traverse the linked list once with a while loop till the next pointer does not become NULL.

Step 3: We do the following procedures while iterating

temp = current->next;

current->next = prev;

prev = current;

current = temp;

We link the temp node to the current node's next node, then reverse the link by linking the current->next node to the previous node. The previous node is then incremented to the current node, and the current node is then incremented to the temp node.

Finally, the head node is returned.

Final thoughts

We learned how to reverse a linked list. Large corporations like Amazon and Google routinely ask about this topic in technical interviews.