Last Updated: 4 Dec, 2020

Reverse Linked List

Easy

Asked in companies

Solve now

Problem statement

You are given a Singly Linked List of integers. You need to reverse the Linked List by changing the links between nodes.

Example:

Input:
2 4 5 -1

Output:
5 4 2 -1

Explanation: 2->4->5 is the initial linked list. If we reverse this, we get 5->4->2.

Input Format :

The first line contains the elements of the singly linked list separated by a single space and terminated by -1. Hence, -1 would never be a list element.

Output Format :

Print the reversed linked list. The elements of the reversed list should be single-space separated, terminated by -1.

Note :

You do not need to print anything, just return the head of the reversed linked list.

Solve now

Approaches

01 Approach

One way is to use recursion to reverse the list. Divide the linked list in two halves, the first node and the rest of the list. Reverse the second half using recursion and append the first half, that is the first node at the end of the reversed linked list. Return the head of the reversed linked list.

Algorithm

If the list contains only one node, return the head of the list.
Else, divide the list into two parts, first node and the rest of the linked list.
Call the reverse for the rest of the linked list.
Append the first node at the end of the reversed linked list, the linked list obtained in step 2.
Return the head of the reversed linked list, obtained in step 4.

Solve now

02 Approach

Reverse the link of each node, starting from the head and moving towards the tail of the linked list. Take three-pointers, ‘curr’, ‘ahead’, ‘prev’. Initialize curr with the head node, ahead, and prev with NULL. Keep on iterating the linked list until ‘curr’ reaches NULL. Store the next node of the current node in ‘ahead’ before changing the next of the current node and point the next of the current node to ‘prev’ (pointer to the node just before the current node). This is the actual reversing of the links in the linked list. Point ‘prev’ node to ‘curr’ node and ‘curr’ node to ‘ahead’ node. At the end return the head of the reversed linked list.

Algorithm

Initialize three pointers prev as NULL, curr as head and ahead as NULL.
Iterate through the linked list and do following
a. Point ‘ahead’ to the next of the current node, ahead = curr->next
b. Point next of the curr node to ‘prev’, curr->next = prev.
c. Point the prev node to the curr node and curr node to the ‘ahead’ node.
Return ‘prev’ , as it will be the head of the reversed linked list and ‘curr’ will be pointing to NULL at this point.

Solve now