#2095

Medium

auto_awesomeLinked-list pointer manipulation

LeetCode Problem Workspace

Delete the Middle Node of a Linked List

Efficiently remove the middle node from a linked list using two-pointer techniques and careful pointer updates to maintain order.

linked list two pointers

Problem Statement

Given the head of a singly linked list, remove the middle node and return the head of the updated list. The middle node is defined as the ⌊n / 2⌋th node in 0-based indexing, where n is the length of the list. Ensure the remaining nodes maintain their original relative order.

For example, with head = [1,3,4,7,1,2,6], the list has 7 nodes, so the middle node is at index 3 with value 7. After removal, the list becomes [1,3,4,1,2,6]. Handle edge cases such as lists with only one or two nodes and verify that the correct node is deleted according to the pattern of fast and slow pointer traversal.

Examples

Example 1

Input: head = [1,3,4,7,1,2,6]

Output: [1,3,4,1,2,6]

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]

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]

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

Solution Approach

Use Fast and Slow Pointers

Initialize two pointers, slow and fast, starting at the head. Move fast by two steps and slow by one step until fast reaches the end. Slow will point to the middle node to delete. This avoids computing the list length separately and ensures efficient single-pass traversal.

Adjust Previous Node's Pointer

Keep track of the node before slow as prev. Once slow reaches the middle node, set prev.next = slow.next to remove the middle node. Handle cases where the list has only one node by returning null, and for two nodes, remove the second node.

Edge Case Handling

Check for empty or single-node lists to return the correct result. Ensure that lists with even lengths remove the lower middle index node. Confirm that all pointer manipulations maintain the integrity of the remaining list.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because each node is visited at most once with the fast and slow pointer traversal. Space complexity is O(1) as no extra data structures are used, only a few pointers for traversal and deletion.

What Interviewers Usually Probe

Expecting an optimal single-pass solution using two-pointer technique.
Looking for correct pointer updates without breaking the list structure.
Interest in handling edge cases like one or two nodes correctly.

Common Pitfalls or Variants

Common pitfalls

Not updating the previous node's next pointer correctly, leaving the middle node in place.
Assuming the list length is known or using extra space unnecessarily.
Misidentifying the middle node in even-length lists by picking the higher index.

Follow-up variants

Delete the nth node from the end using a similar fast-slow pointer approach.
Remove multiple nodes at regular intervals using pointer manipulation patterns.
Delete the middle node in a circular linked list while maintaining the loop.

FAQ

How do I identify the middle node in a linked list using pointers?

Use a fast pointer moving two steps and a slow pointer moving one step. When the fast pointer reaches the end, the slow pointer points to the middle node.

What happens if the linked list has only one node?

If the list has one node, removing the middle node results in an empty list, so you should return null.

How do I handle even-length linked lists for middle node deletion?

For an even-length list, remove the lower middle node at index ⌊n / 2⌋ using the same fast-slow pointer approach.

Can this method be done in one pass?

Yes, using the fast and slow pointer technique allows locating and deleting the middle node in a single traversal.

Does deleting the middle node require extra space?

No, this approach only uses a few pointers for traversal and deletion, resulting in O(1) space complexity.

terminal

Solution

Solution 1: Fast and Slow Pointers

The fast and slow pointer technique is a common method used to solve problems related to linked lists. We can maintain two pointers, a slow pointer $\textit{slow}$ and a fast pointer $\textit{fast}$. Initially, $\textit{slow}$ points to a dummy node, whose $\textit{next}$ pointer points to the head node $\textit{head}$ of the list, while $\textit{fast}$ points to the head node $\textit{head}$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(next=head)
        slow, fast = dummy, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        slow.next = slow.next.next
        return dummy.next

Continue Practicing

#2130 maximum twin sum of a linked list #1721 swapping nodes in a linked list #2105 watering plants ii