Reversing A Linked List

In this article let's learn how to reverse a  linked list(iterative method) in an efficient and easy manner. This problem is a part of data structures(Linked Lists). This reversing a linked list problem is frequently asked in many of the interviews.

Now let's see what a linked list is and how it works along with its advantages.

What is a linked list?

• A linked list is a data structure that stores a linear collection of data elements, called nodes which are stored in memory at random locations.
• In the linked list, each node is divided into two parts.
• The first part contains the data of the element.
• The second part contains the address of the next node in the list.

Advantages of a linked list

• A linked list is a dynamic data structure, so it is easy to allocate and deallocate memory.
• No memory wastage.
• Insertion and deletion of elements are easier.
• Using a linked list one can implement sack and queue.

This problem was frequently asked in big tech company interviews, so now let's get into the problem and its optimized solution.

Given the head of a singly linked list, reverse the list, and return the reversed list.

Input: 1->2->3->4->NULL

Output: 4->3->2->1->NULL

Method-1:

Iterative Method:

Let's focus on the function ReverseLinkedList():

->Initialize three-pointers prev, curr, nxt.

->Now assign head to curr and nxt, assign NULL to prev.

->Now iterate through the loop :

• change the next of nxt pointer(nxt->next=next).
• store prev node in next of curr node(curr->next=prev).
• now assign curr node to prev node(prev=curr).
• At last assign nxt node to curr(curr=nxt).

 ->Now assign node prev to head(head=prev)

->return head.

Program to reverse a linked list:

SinglyLinkedListNode* ReverseLinkedList(SinglyLinkedListNode* head)

 {

     SinglyLinkedListNode *curr=head;

     SinglyLinkedListNode *nxt=head;

      SinglyLinkedListNode* prev=0;

     while(nxt!=0)

     {

        nxt=nxt->next;

        curr->next=prev;

        prev=curr;

        curr=nxt;

     }

     head=prev;

     return head;

}

Method-2:

Recursive Method:

• Divide the list into two parts first node and the rest of the linked list.
• Call reverse for the rest of the linked list.
• Now link the rest of the linked list to the first node.
• At last fix head.

SinglyLinkedListNode* reverse(SinglyLinkedListNode* head)

    {

        if (head == NULL || head->next == NULL)

            return head;

 

        

        SinglyLinkedListNode* rest = reverse(head->next);

        head->next->next = head;

 

        head->next = NULL;

 

        

        return rest;

    }




Both the methods run in O(n) time complexity and O(1) space complexity.

We have come to an end so if you guys like this article, please share it with your friends.

Some more articles that you may like:

• singly linked list in java
• Merge two sorted linked lists
• Array in c++
• Queue in java
• Stack in java