Delete middle node
You have been given a singly Linked List of integers. Your task is to delete the middle node of this List.

Note:

1. If there is no middle node in the list to delete, return an empty list (i.e. NULL). 2. If there are two middle nodes in the list, delete the first one.

Follow up :

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?

Input format :

The first line of input contains an integer 'T' representing the number of test cases or queries to run. Then the test case follows. The only line of each test case contains the elements of the singly linked list separated by a single space and terminated by -1. Hence, -1 would never be a list element.

Output format :

For each test case, print the resultant linked list after performing the required operation denoted as the elements separated by a single space and terminated by -1. Print output of each test case in a separate line.

Note :

You are not required to print the output, it has already been taken care of. Just implement the function.

Constraints :

1

Question

Delete middle node

You have been given a singly Linked List of integers. Your task is to delete the middle node of this List.

Note:

1. If there is no middle node in the list to delete, return an empty list (i.e. NULL).
2. If there are two middle nodes in the list, delete the first one.

Follow up :

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?

Input format :

The first line of input contains an integer 'T' representing the number of test cases or queries to run. Then the test case follows.

The only line of each test case contains the elements of the singly linked list separated by a single space and terminated by -1. Hence, -1 would never be a list element.

Output format :

For each test case, print the resultant linked list after performing the required operation denoted as the elements separated by a single space and terminated by -1.

Print output of each test case in a separate line.

Note :

You are not required to print the output, it has already been taken care of. Just implement the function.

Constraints :

1 <= T <= 100
0 <= L <= 5000
1 <= data <= 10^9 and data != -1

Where 'L' is the number of nodes in the Linked List.

Time Limit: 1 sec

Accepted Answer

Count Nodes

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:

'PREV_NODE' -> next = ‘MIDDLE_NODE’ -> next.
delete 'MIDDLE_NODE’

Space Complexity: O(1)Explanation:

O(1).

Constant extra space is used.

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of nodes in the linked list.

As we are traversing the list only two times so, the overall time complexity will be O(N).

Accepted Answer

Two Pointers

The idea here is to use two pointers i.e. ‘SLOW’ and ‘FAST’ and both will traverse in the linked list from beginning to end but at a different pace. The ‘SLOW’ pointer will move normally in the linked list, one step at a time. The other ‘FAST’ pointer will move two steps at a time.

Now, when the ‘FAST’ pointer reaches the end of the list, we know that the ‘SLOW’ pointer is only halfway through because the speed is half for the ‘SLOW’ pointer. Hence, the ‘SLOW’ pointer must be standing at the middle node, so we delete it.

As mentioned earlier, we will be using the traditional method of deleting the node from the list which is to have a pointer to the previous node of the node which is going to be deleted. Also, we will save the pointer to the middle node to deallocate the memory. For that, we can maintain a different pointer ‘PREVIOUS’ which will be used to track the previous node of the ‘SLOW’ pointer. In simple words:

'PREVIOUS' -> next = 'SLOW' -> next
delete 'SLOW'