Last Updated: 14 Jan, 2021

Reverse a Sublist of Linked List

Easy
Asked in companies
HSBCFacebookInfosys

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

Approaches

01 Approach

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

02 Approach

  • 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 
    • Return newHead.

03 Approach

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