Reverse A LL

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
58 upvotes
Asked in companies
PhonePeMicrosoftHCL Technologies

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’.

Detailed explanation ( Input/output format, Notes, Images )
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?
Sample Input 1 :
2
1 3 2 4 6 5 -1
2 3
1 3 7 4 -1
2 4
Sample Output 1 :
1 2 3 4 6 5
1 4 7 3
Explanation For Sample Input 1 :
For first test case :

Reversing nodes 2 and 3 : 2 3
Resultant linked list : 1 2 3 4 6 5   

For second test case :

Reversing nodes 2 and 4 : 4 7 3
Resultant linked list : 1 4 7 3
Sample Input 2 :
2
1 3 4 5 -1
1 2
1 2 2 -1
2 3
Sample Output 2 :
3 1 4 5
1 2 2
Hint

Traverse till the node at position ‘LOW’ recursively and then reverse the linked list.

Approaches (2)
Recursive 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 :

 

  1. Base case :
    • If ‘HEAD’ is equal to ‘NULL’ or next of ‘HEAD’ is equal to ‘NULL’.
      • Return ‘HEAD’.
  2. Base case :
    • If ‘LOW’ is equal to ‘HIGH’
      • Return ‘HEAD’.
  3. 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’.
  4. 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’
Time Complexity

O(N), where ‘N’ is the number of nodes in the linked list.
 

We traverse the linked list once recursively to reverse the linked list. Therefore, the overall time complexity will be O(N).

Space Complexity

O(N), where ‘N’ is the number of nodes in the linked list.

 

The recursive stack can contain the length of the linked list. Therefore, the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Reverse A LL
Full screen
Console