Reverse a Sublist of Linked List

Posted: 14 Jan, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

You are given a linked list of 'N' nodes. Your task is to reverse the linked list from position 'X' to 'Y'.

For example:
Assuming, the linked list is 10 -> 20 -> 30 -> 40 -> 50 -> 60 -> NULL. X = 2 and Y = 5. On reversing the given linked list from position 2 to 5, we get 10 -> 50 -> 40 -> 30 -> 20 -> 60 -> NULL.
Input Format:
The first line of input contains an integer ‘T’ representing the number of test cases.

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

The second line of every test case contains two space-separated integers, 'X' and 'Y', denoting the positions in the linked list.
Output Format:
For each test case, the resulting linked list is printed.

Print the output of each test case in a separate line. 
Note:
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Follow up:
Can you solve it in place and in one pass?
Constraints:
1 <= T <= 100   
1 <= N <= 10^6
1 <= X, Y <= N
1 <= data <= 10^7 

Time Limit: 1 sec
Approach 1
  • A brute force approach could be to copy the sublist (from X to Y) into a new list.
  • Reverse the newly created list.
  • Now, we have the reversed form of the sublist. So, copy this back to the original linked list.
  • Return the head of the list.

Note:

  • This approach doesn’t reverse the sublist in-place, instead creates a new copy of the sublist.
  • Also, we are traversing the list twice (once to create a new list and once to copy it back to the original list)
Try Problem