Last Updated: 5 Feb, 2021
Rotate DLL
Moderate
Asked in company
You are given a doubly-linked list with 'N' nodes, rotate the linked list counter-clockwise by 'K' nodes. 'K' is a positive integer and is smaller than the number of nodes in the linked list, that is 'N'.
A doubly linked List (DLL) contains an extra pointer, called the previous pointer, together with the next pointer and data which are there in the singly linked list such that both forward and backward navigation is possible.
For example
The given linked list is -
If K = 3, then the list after rotating it by K nodes is:
Note:
1. The value of any node in the linked list will not be equal to -1.
Input format :
The first line of input contains an integer ‘T’ denoting the number of test cases.
The first line of each test case contains 'N' space-separated integers representing the value of each node. -1 at the end denotes NULL pointer.
The second line of each test case contains a single positive integer 'K'.
Output format :
For each test case, in a separate line, print the final rotated linked list.
Note:
You don’t have to print anything; it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 5
1 <= N <= 3000
1 <= K < N
-10 ^ 7 <= data <= 10 ^ 7
where ‘T’ is the total number of test cases, 'N' is the total number of nodes in the linked list and ‘data’ is the value of any node of the linked list.
Approaches
The idea is to use an extra list to first store the last N - K elements then store the starting K elements.
- Declare an integer variable 'count' and initialize it with 0.
- First, iterate through the list and keep a count for the nodes, that is, iterate it till the count becomes equal to K and store that pointer to the node.
- Now make a new linked list and start storing nodes from the pointer that is stored above till the last node of the original list.
- Again iterate through the initial list from starting till the count becomes equal to 0 and keep storing these nodes in the new list.
Keep decreasing count by 1. - Return the head of the new list.
The idea is to change the link of the pointers after the Kth node. We need to change next of Kth node to NULL next of last node to previous head node, and prev of head node to last node and finally change head to (K+1)th node and previous of new head node to NULL.
- We will store three pointers that are for the Kth node and the node ahead of it that is (K + 1)th node and the last node .
- Now iterate till the Kth node and store the pointer to that node.
- For the last pointer iterate till the last of the linked list and store the last node.
- Change the next of the Kth node to NULL and because this will be the last node in the final rotated list.
- Now, link the next pointer of the last node to the current head node to attach it to the broken list.
- Now update the head node to the (K + 1)th node and previous to NULL because the previous pointer of head node in doubly linked list is NULL.
- Return the updated head.