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