New update is available. Click here to update.

Last Updated: 3 Oct, 2020

Difficulty: Easy

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

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

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

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

```
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?
```

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’

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'

SIMILAR PROBLEMS

Deletion In Doubly Linked List

Posted: 22 Apr, 2022

Difficulty: Easy

Insertion In Doubly Linked List

Posted: 24 Apr, 2022

Difficulty: Easy

LRU Cache

Posted: 10 Sep, 2022

Difficulty: Moderate

Delete Nodes On Regular Intervals

Posted: 19 Dec, 2022

Difficulty: Ninja

Add One To Linked List

Posted: 19 Dec, 2022

Difficulty: Hard

Popular Interview Problems: