Problem

Submissions

Hints & solutions

Discuss

Delete Middle Node

Easy

0/40

Average time to solve is 15m

Contributed by

75 upvotes

Asked in companies

Problem statement

Given a singly linked list of 'N' nodes. Your task is to delete the middle node of this list and return the head of the modified list.

However, if the list has an even number of nodes, we delete the second middle node

Example:

If given linked list is 1->2->3->4 then it should be modified to 1->2->4.

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line contains an integer 'N', the size of the linked list.
The second line contains 'N' space-separated integers.

Output Format :

The output contains all the nodes of linked list except the middle node. If the list is empty, '-1' will be printed.

Note :

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

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?

Sample Input 1 :

5
1 2 3 4 5

Sample Output 1 :

1 2 4 5

Explanation to Sample Input 1 :

We can clearly see that there are 5 nodes in the linked list therefore the middle node is the node with value '3'.

Sample Input 2 :

1
2

Sample Output 2 :

-1

Explanation to Sample Input 1 :

We can clearly see that there is only one node in the linked list.
Therefore, after deleting that one node, the linked list becomes empty, resulting in an output of -1.

Constraints :

1 <= N <= 10^3
0 <= data <= 10^3 

Where 'N' is the length of the linked list.

Time Limit: 1 sec

Hint 1

Hint 2

The middle node has around half the total number of nodes towards its left side. Can you use this idea somehow to solve the problem?

Approaches (2)

Approach 1

Approach 2

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’

Time Complexity

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).

Space Complexity

O(1).

Constant extra space is used.

(100% EXP penalty)

Delete Middle Node

Console