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

The task is to delete the middle node of a singly linked list of integers.

If the linked list is empty or has only one node, there is no middle node to delete.
To delete the middle node, we need to find the middle node and update the pointers of the previous and next nodes.
To find the middle node in one traversal, we can use two pointers - a slow pointer and a fast pointer.
The slow pointer moves one node at a time, while the fast pointer moves two nodes at a time.
When the fast pointer reaches the end of the list, the slow pointer will be at the middle node.
Once the middle node is found, update the pointers of the previous and next nodes to skip the middle node.
Return the updated linked list after deleting the middle node.

Accepted Answer

Approach 1 :

1) Count the number of nodes in a linked list.
2) Delete n/2’th node using the simple deletion process.

TC : O(N) , N=number of nodes in the Linked List
Two traversals of the linked list is needed

SC : O(1)

Approach 2 :

1) The idea is to use two pointers, slow_ptr, and fast_ptr.
2) Both pointers start from the head of list. When fast_ptr reaches the end, slow_ptr reaches middle.
3) Keep track of the previous middle so the middle node can be deleted.

TC : O(N)
Single Traversal of the linked list is required

SC : O(1)

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'