'Coding has over 700 languages', '67% of programming jobs aren’t in the
technology industry', 'Coding is behind almost everything that is powered
by electricity'

Problem of the day

Last Updated: 14 Jan, 2021

Easy

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

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

```
For each test case, the resulting linked list is printed.
Print the output of each test case in a separate line.
```

```
You don’t need to print anything. It has already been taken care of. Just implement the given function.
```

```
Can you solve it in place and in one pass?
```

```
1 <= T <= 100
1 <= N <= 10^6
1 <= X, Y <= N
1 <= data <= 10^7
Time Limit: 1 sec
```

- 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)

- The problem can be solved by using recursion.
- First, recursively move to the node at position ‘X’.
- On reaching the node ‘X’, recursively reverse the next Y - X + 1 nodes (including X).
- In this way, we have reversed the list from position X to Y.
- Return the head of the resulting linked list.

Algorithm:

- Let’s assume our recursive function is
**reverseSublist(head, X, Y).** - Initially, we call the function with
**head**pointing to the start of the given linked list, and**X and Y**storing the given positions of the linked list. **Base Condition: If X = Y,**the sublist has a length of 1. So, no need to reverse, just return**head.**- Now,
**If X > 1,**then we haven’t reached the node at position X. So, recur for the remaining nodes by calling:**head->next = reverseSublist(head->next, X-1, Y-1)**- We decrease X every time we move to the next node.
- But we also decrease Y so that the number of nodes which we want to reverse stays constant i.e. (Y-1)-(X-1)+1 = Y-X+1.

**Otherwise X = 1**, hence, we have reached the node at position ‘X’. Now we just need to reverse the next Y-X+1 nodes (including X). We can achieve this as follows:- Store the address of the next node in a temporary variable i.e.
**temp = head->next.** - We reverse the remaining nodes by recursively calling the function as
**reverseSublist(head->next, 1, Y-1).**The function will return the pointer to the start of the reversed list (excluding the current node). Store the returned value in a variable, say**newHead.** - Now, update the pointers as follows:
- Let
**tempNext = temp->next.** **temp->next = head.****head->next = tempNext**

- Let
**Return newHead.**

- Store the address of the next node in a temporary variable i.e.

- We can avoid the extra space used in recursion by reversing the sublist iteratively.
- In order to do this, we first add a
**dummy**node at the start of the linked list. This is done so that our approach works correctly even when X = 1. - Now, create a variable ‘
**pre’**and make it point to the node present at position X-1. In case X=1,**pre**will point to**dummy**. - Create two new variable
**start**and**tail**and make them point to nodes present at position X and X+1, respectively, i.e.:**start = pre -> next.****tail = start -> next.**

**start**always points to the last node of the sublist which has been reversed, and**tail**points to the next node which needs to be included in the reversed sublist.- Now, we need to reverse the sublist. In each step, we are increasing the size of the reversed sublist by 1. As we need to reverse Y-X+1 nodes (including start), we repeat the following steps Y-X times (as the first node is already included in the reversed sublist).
- To add the next node to the reversed sublist we update the pointers as follows:
**start -> next = tail -> next.****tail -> next = pre -> next.****pre -> next = tail.****tail = start -> next.**- In this way, we keep inserting the
**tail**node between the node**pre**and**start.** - And keep moving the tail node to make it point to the next node which we need to add.
- Making
**start->next point**to**tail->next**ensures that start keeps pointing to the last node of the sublist.

**Dummy -> next**points to the start of the resulting linked list.- So, return
**Dummy -> next.**

Similar problems

Deletion In Doubly Linked List

Easy

Posted: 22 Apr, 2022

Deletion In Doubly Linked List

Easy

Posted: 22 Apr, 2022

Insertion In Doubly Linked List

Easy

Posted: 24 Apr, 2022

Insertion In Doubly Linked List

Easy

Posted: 24 Apr, 2022

LRU Cache

Moderate

Posted: 10 Sep, 2022

Delete Nodes On Regular Intervals

Ninja

Posted: 19 Dec, 2022

Add One To Linked List

Hard

Posted: 19 Dec, 2022