Delete the Middle Node of a Linked List
Delete the Middle Node of a Linked List is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Two Pointers pattern, in the Fixed Separation (Nth Node from End) subpattern.
Problem statement
You are given the head of a linked list. Delete the middle node, and return the head of the modified linked list.
The middle node of a linked list of size n is the n / 2 th node from the start using 0-based indexing, where x denotes the largest integer less than or equal to x.
- For n = 1, 2, 3, 4, and 5, the middle nodes are 0, 1, 1, 2, and 2, respectively.
Example 1:
Input: head = [1,3,4,7,1,2,6] Output: [1,3,4,1,2,6] Explanation: The above figure represents the given linked list. The indices of the nodes are written below. Since n = 7, node 3 with value 7 is the middle node, which is marked in red. We return the new list after removing this node.
Example 2:
Input: head = [1,2,3,4] Output: [1,2,4] Explanation: The above figure represents the given linked list. For n = 4, node 2 with value 3 is the middle node, which is marked in red.
Example 3:
Input: head = [2,1] Output: [2] Explanation: The above figure represents the given linked list. For n = 2, node 1 with value 1 is the middle node, which is marked in red. Node 0 with value 2 is the only node remaining after removing node 1.
Constraints:
- The number of nodes in the list is in the range [1, 105].
- 1 <= Node.val <= 105
Topics and companies
Topics: Linked List, Two Pointers.
How to practise Delete the Middle Node of a Linked List on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.
Open Delete the Middle Node of a Linked List in the code editor, or read the Delete the Middle Node of a Linked List editorial for a worked solution with its approach and complexity analysis.
Where Delete the Middle Node of a Linked List sits in the DSA pattern sheet
- Two Pointers pattern guide
- Fixed Separation (Nth Node from End) subpattern
- The full DSA patterns sheet
- All coding practice problems
Problems related to Delete the Middle Node of a Linked List
Other problems that use the same Fixed Separation (Nth Node from End) and Two Pointers techniques:
- Middle of the Linked List — Easy, same subpattern
- Remove Nth Node From End of List — Medium, same subpattern
- Backspace String Compare — Easy, same pattern
- Boats to Save People — Medium, same pattern
- Container With Most Water — Medium, same pattern
- Crawler Log Folder — Easy, same pattern