If given linked list is 1->2->3->4 then it should be modified to 1->2->4.
The first line contains an integer 'N', the size of the linked list. The second line contains 'N' space-separated integers.
The output contains all the nodes of linked list except the middle node. If the list is empty, '-1' will be printed.
You are not required to print the output, it has already been taken care of. Just implement the function.
Try to solve this problem in O(N) time complexity and O(1) space complexity. Can you solve it in only one traversal of the Linked List?
The idea is simple and naive. We will first count the total number of nodes in the linked list (say ‘N’). Now, we know that the ceil('N' / 2)th node is our middle node of the linked list.
So, now we will follow the traditional algorithm for deleting a node from the linked list. We will traverse till the previous node of the node which is going to be deleted, and point the next pointer of the previous node to the next node of the middle node. Also, we will save the pointer to the middle node to deallocate the memory. In simple words:
Deletion In Doubly Linked List
Insertion In Doubly Linked List
Delete Nodes On Regular Intervals
Add One To Linked List