Last Updated: 9 Sep, 2021

Reverse A LL

Moderate

Asked in companies

Solve now

Problem statement

Ninjas is practicing problems on the linked list. He came across a problem in which he has given a linked list of ‘N’ nodes and two integers, ‘LOW’ and ‘HIGH’. He has to return the linked list ‘HEAD’ after reversing the nodes between ‘LOW’ and ‘HIGH’, including the nodes at positions ‘LOW’ and ‘HIGH’.

Input Format :

The first line of input contains an integer ‘T’, the number of test cases.

The first line of each test case contains the linked list separated by space and terminated by -1.

The second line of each test case contains two space-separated integers, representing the ‘LOW’ and ‘HIGH’ integers, respectively.

Output Format :

For each test case, print the updated linked list.

Output for each test case will be printed in a separate line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= N <= 3*10^3
1 <= LOW <= RIGHT <= N

Time Limit: 1 sec

Follow Up: Can you solve it using constant space i.e O(1) space complexity?

Solve now

Approaches

01 Approach

The basic idea is to traverse the linked list recursively until we reach ‘LOW’ in our linked list. Then we will reverse the linked list by changing the pointers.

Here is the algorithm :

Base case :
- If ‘HEAD’ is equal to ‘NULL’ or next of ‘HEAD’ is equal to ‘NULL’.
  - Return ‘HEAD’.
Base case :
- If ‘LOW’ is equal to ‘HIGH’
  - Return ‘HEAD’.
Check if ‘LOW’ is greater than 1. (To reach node at ‘LOW’ position)
- Recursively call the function on the node next to ‘HEAD’ and by decreasing the value of ‘LOW’ and ‘HIGH’ by 1 and update next of ‘HEAD’ by the value returned by the recursive function.
- Return ‘HEAD’.
Else
- Recursively call the function on the node next to ‘HEAD’ by passing the value of ‘LOW’ as 1 and by decreasing the value of ‘HIGH’ by 1 and store the value returned by the recursive function in a new node (say, ‘TEMP’)
- Create a new node (say, ‘NEXT’) and initialize it with the node next to next of ‘HEAD’. (Reversing the linked list)
- Update next of next of ‘HEAD’ by ‘HEAD’.
- Update next of ‘HEAD’ by ‘NEXT’
- Return ‘TEMP’

Solve now

02 Approach

The idea is to iteratively traverse till the node present at position ‘LOW’ while decreasing the ‘LOW’ and ‘HIGH’ integers. Then we will reverse the linked list till ‘HIGH’ is greater than zero. After reversing, we will change the pointers adjacent to the reversed linked list after reversing to get the resultant linked list.

Here is the algorithm :

Base case :
- If ‘HEAD’ is equal to ‘NULL’.
  - Return ‘HEAD’.
Create a new node (say, ‘CURR’) and initialize it with ‘HEAD’.
Create a new node (say, ‘PREV’) and initialize it with ‘NULL’.
Run a loop till ‘LOW’ is greater than 1. (To reach node at ‘LOW’ position)
- Update ‘PREV’ with ‘CURR’.
- Update ‘CURR’ to next of ‘CURR’.
- Decrease ‘LOW’ by 1.
- Decrease ‘HIGH’ by 1.
Create a new node (say, ‘END’) and initialize it with ‘CURR’.
Create a new node (say, ‘START’) and initialize it with ‘PREV’.
Run a loop till ‘HIGH’ is greater than 0. (To reverse linked list between two positions)
- Create a new node (say, ‘TEMP’) and initialize it with a node next to ‘CURR’.
- Update next of ‘CURR’ to ‘PREV’.
- Update ‘PREV’ to ‘CURR’.
- Update ‘CURR’ to ‘TEMP’.
- Decrease ‘HIGH’ by 1.
Check if ‘START’ is ‘NULL’ (Change pointers adjacent to reversed linked list.)
- Update ‘HEAD’ to ‘PREV’.
Else
- Update next of ‘START’ to ‘PREV’.
Update next of ‘END’ to ‘CURR’.
Finally, return ‘HEAD’.

Solve now