Problem

Submissions

Hints & solutions

Discuss

Reverse a Sublist of Linked List

Easy

0/40

Average time to solve is 10m

Contributed by

7 upvotes

Asked in companies

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

2
10 20 30 40 50 60 -1
2 5
1 2 5 8 9 7 -1
2 4

Sample Output 1:

10 50 40 30 20 60 -1
1 8 5 2 9 7 -1

Explanation of the Sample Input1:

For the first test case, refer to the example explained above.

For the second test case, the linked list is 1 -> 2 -> 5 -> 8 -> 9 -> 7 -> NULL and X = 2 and Y = 4. On reversing the given linked list from position 2 to 4, we get 1 -> 8 -> 5 -> 2 -> 9 -> 7 -> NULL.

Sample Input 2:

2
4 2 5 4 2 2 -1
3 3
1 2 3 4 -1
1 4

Sample Output 2:

4 2 5 4 2 2 -1
4 3 2 1 -1

Hint 1

Hint 2

Hint 3

Reverse the sublist by creating a new list.

Approaches (3)

Approach 1

Approach 2

Approach 3

Brute Force

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)

Time Complexity

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

In the worst case, we would traverse the complete list. Hence, the overall time complexity is O(N).

Space Complexity

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

In the worst case, O(N) extra space is required for storing the sublist. Hence, the overall space complexity is O(N).

(100% EXP penalty)

Reverse a Sublist of Linked List

Console