Delete middle node

Posted: 3 Oct, 2020
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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
Approach 1

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’ 
Try Problem