Problem of the day
You are given a Doubly Linked List of ‘N’ positive integers. Your task is to delete a node at position ‘POS’ in the linked list.
Note:Assume that the Indexing for the linked list starts from 0.
EXAMPLE:
Input: ‘N’ = 5, 'LIST' = [1, 1, 2, 3, 4, -1], ‘POS’ = 1.
Output: 1 < - > 2 < - > 3 < - > 4
Here in the given list, we can see that the node at position 1 is deleted.
The first line of input contains a single integer T, representing the number of test cases or queries to be run.
The second line of the test case contains space-separated integers which are the nodes of the linked list and each line ends with -1 to indicate that the sublist is over. Thus, -1 will never be a linked list element.
The third line of each test case contains a single integer ‘POS’ denoting the position at which the node has to be deleted.
Output format :
The first and only line of each test case in the output contains the linked list after deleting the required element.
Note :
You don't need to print anything. It has already been taken care of. Just implement the given function.
1 <= ‘T’ <= 10
2 <= ‘N’ <= 10^4
0 <= ‘POS < N
1 <= ‘data’ <= 10^7
Where 'N' is the size of the doubly linked list, and ‘data’ is the Integer data of the doubly linked list.
Time Limit: 1 sec
2
1 1 2 3 4 -1
1
1 2 -1
1
1 2 3 4
1
For the first test case,
‘N’ = 5, 'LIST' = [1, 1, 2, 3, 4, -1], ‘POS’ = 1.
After deleting the node at position 1 the list will be:
1 < - > 2 < - > 3 < - > 4.
For the second test case,
‘N’ = 2, 'LIST' = [1, 2, -1], ‘POS’ = 1.
After deleting the node at position 1 the list will be:
1.
2
1 2 3 -1
0
3 4 4 -1
2
2 3
3 4
Can you figure out how to delete a node between two nodes?
If ‘POS’ is 0 means that we have to delete a node at the beginning of the linked list means we have to make the 2nd node as the head node so just set ‘head’ = ‘head → next’ and ‘head → prev’ = ‘NULL’.
If ‘POS’ is ‘N - 1’ means that we have to add a node at the end of the linked list so just traverse to position ‘N - 2’ of the linked list and set the ‘NEXT’ of the node as ‘NULL’.
If ‘POS’ is in the range [1, N - 2] then we simply traverse to position ‘POS’ and link the previous node of the current node to the next node of the current node by setting ‘curr->prev->next’ = ‘curr->next’ and ‘curr->next->prev’ = ‘curr->prev’.
Algorithm :
O(N), where ‘N’ is the size of the linked list.
We are traversing the linked list two times in the worst case.
Hence, the overall time complexity will be O(N).
O(1)
We are not using any extra space.
Hence the overall space complexity will be O(1).